Powered by OpenAIRE graph
Found an issue? Give us feedback
addClaim

Coloured Graph Decompositions

Authors: Waterhouse, M A;

Coloured Graph Decompositions

Abstract

Let G be a graph in which each vertex has been coloured using one of k colours, say C1, c2, …, ck. If a graph H in G has ni vertices coloured ci i = 1, 2, ... , k, and |ni –nj| 5, there exists at least one 5-cycle decomposition of Kv which cannot be equitably 2-coloured. In addition, we completely settle the existence question for equitably 2-colourable m-cycle decompositions of Kv - F and for equitably 3-colourable m-cycle decompositions of Kv and Kv - F, where m Є { 4, 5, 6}. We also provide upper bounds on admissible values of v for existence of equitably (m - 1)-colourable m-cycle decompositions of Kv and Kv - F. In Chapter 3, we partially generalise our results on equitably 2-colourable even-length cycle decompositions of Kv - F. Except for the case where v(v - 2)/2 is an odd multiple of m and v = m = 4 (mod8), we show that if the obvious necessary conditions are satisfied then there exists an equitably 2-coloured m-cycle decomposition of Kv - F for even m. In Chapter 4, we completely settle the existence question for equitably 2-colourable 3- and 5-cycle decompositions of Kp(n), and for equitably 2-colourable 4- and 6-cycle decompositions of Kn1,n2, ... ,np,· In addition, we completely settle the existence question for equitably 3-colourable m-cycle decompositions of Kp(n), for m Є {3, 4, 5}. In Chapter 5, we completely settle the existence question for equitably 2- and 3-colourable 3-cube decompositions of Kv, Kv - F and Kx,y· We also consider other types of coloured graph decompositions. Suppose that the vertices of Kv, have been coloured with at most two colours. Let C1 C2, . . .Cm denote the colouring of the m-cycle (x1,x2, . . . ,xm) which assigns the colour Ci to the vertex xi for i = 1, 2, . . . , m, where Ci Є {black, white}. We let T be the set of all possible such colourings and we let S C T. If ɧ is an m-cycle system such that the colouring type of every m-cycle in ɧ is in S, and every colouring type in S is represented in ɧ, then we say that ɧ has proper colouring Type S. In Chapter 6, we completely settle the existence question for 4-cycle decompositions with proper colouring Type S for all possible S. In Chapter 7, we completely settle the existence question for 5-cycle decompositions with proper colouring Type S for all S when |S| = 1, and for many |S| when |S| = 2. For the remaining S, where |S| = 2, we determine some necessary conditions for existence of such decompositions.

Country
Australia
Related Organizations
Keywords

Graph theory, 780101 Mathematical sciences, School of Physical Sciences, Set Theory, Lattices And Combinatorics, 230101 Mathematical Logic, L, 230101 Mathematical Logic, Set Theory, Lattices And Combinatorics

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!