For ω(G) ≥ Δ(G), the conjecture is simply the statement that G may be colored with Δ(G) + 1 colors. For ω(G) = Δ(G) - 1, its truth follows from the theorem of Brooks .
If G is triangle-free, ω(G) = 2, the conjecture is asymptotically true in a much stronger form, as shown by A.Johansson, who proved that there is a constant c > 0 such that the list-chromatic number of G is bounded by
If Δ(G) is as large as possible, Δ(G) = |V(G)| - 1, then the truth of the conjecture is a consequence of classical matching theory, as observed by Reed .
Reed  also posed a number of similar, most of them weaker, conjectures.
Gyárfás  proved, based on a theorem of Krusenstjerna-Hafstrøm and Toft , that if every even cycle of a graph spans a bipartite subgraph, then the graph is 3-colorable.
For k=4, an example G due to T.R.Jensen may be described as follows. First, let H be the graph of the usual 5x5 chessboard, that is, the four corners of each square are vertices of H, and the four sides are edges that join the corresponding vertices. Thus H has 36 vertices, 16 of which are of degree 4, with the remaining vertices forming the boundary C of the chessboard, where C is a cycle of length 20. Now let G be the graph obtained from H by adding 10 additional edges, joining each vertex on C to its antipode; the vertex to which it has distance 10 on C. Then all vertices of G have degree 4, except the four corners of the board, which have degree 3. It is not difficult to find a 4-coloring of G with the desired property, in which the color classes consist of 3x3 square arrangements, tilted by 45o with respect to the original board, each class containing one of the four corners of the board. The fact that G is 4-chromatic is more difficult to prove; since G can be embedded in the projective plane as a quadrangular tessalation, this follows from arguments similar to those employed by Gallai [1963a] for constructing examples of 4-regular 4-critical graphs (see Problem 5.2).
For k ≥ 5, it is not known whether such graphs exist. It is interesting to note that if a k-chromatic graph G allows a k-coloring of this type, and if A is one of the color-classes of such a coloring, then G - A - N(A) is again a (k-1)-chromatic example, where N(A) denotes the set of neighbors of A. In particular, it follows that such a G cannot have an odd cycle of length less than 9.