On an open problem in defective graph colourings
Abstract
The Δ(d)-chromatic number of a graph G, denoted by Xd Δ(G), is the smallest number of colours with which the vertices of G may be coloured so that the subgraph induced by each colour class has maximum degree at most d. The Δ-chromatic sequence of a graph G is merely the sequence (XdΔ(G))d ∞=0. It is known that if (xi)i∞=0 is the Δ-chromatic sequence of some graph G, then Xℓ = 1 for some positive integer ℓ, and xj, ≤ xi ≤ xj [(j + 1)/(i + 1)1] if 0 ≤ i < j. However, it is not known whether these necessary conditions for Δ-chromatic sequences of graphs are also sufficient. In this paper a subset of essential sequences of the full set of sequences satisfying these necessary conditions is isolated; this subset may be used in an attempt at establishing sufficiency, or otherwise, of the above necessary conditions.
