NEW PROBLEMS
Graph Coloring Problems

Reed's ω, Δ, and χ conjecture

Can every graph G be colored with at most ( ω(G) + Δ(G) )/2 + 1 colors?

Reed [1997] asked this question and conjectured that the answer is positive. As a first step towards the conjecture, Reed [1997] proved that if Δ(G) is large enough, and if ω(G) k for some k [ ( 1 - 1/70000000 )Δ(G) ], then G has chromatic number at most ( k + Δ(G) + 1 )/2.

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 [1941].

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

cΔ(G) / log Δ(G),
(see also Problem 4.6).

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 [1997].

Reed [1997] also posed a number of similar, most of them weaker, conjectures.

Reference

[1997] Reed, B. ω, Δ, and χ. J. Graph Theory 27 (1997) 177-212.

Graphs whose paths span 3-colorable subgraphs

If each path of a graph spans a 3-colorable subgraph, is the graph then c-colorable, where c is a constant? Perhaps this is true with c = 4?

That such a constant exists is a conjecture of Gyárfás [1997]; it is the special case r =3 of a problem raised by P.Erdös and A.Hajnal: If every odd cycle of a graph spans a subgraph with chromatic number at most r then the chromatic number of the graph is bounded by a function of r.

Gyárfás [1997] proved, based on a theorem of Krusenstjerna-Hafstrøm and Toft [1980], that if every even cycle of a graph spans a bipartite subgraph, then the graph is 3-colorable.

References

[1997] Gyárfás, A. Fruit Salad, Electronic Journal of Combinatorics 4 (1997).
[1981] Krusenstjerna-Hafstrøm, U., and B. Toft, Special subdivisions of K4 and 4-chromatic graphs, Monatsh. Math. 89 (1980) 101-110.

Graphs whose color-classes have independent neighborhoods

Is there for every integer k > 0 a k-chromatic graph with some k-coloring for which the neighbors of each of the k color-classes form an independent set?

The question was first discussed by N.J.A.Harvey and U.S.R.Murty at the University of Waterloo in a weaker form, when it was only required that the neighbors of each color-class should induce a subgraph of chromatic number less than k-1 [personal communication from U.S.R. Murty in 1998]. The ultimate form of the question, as stated above, arose after discussions with B.Toft, who also pointed out that the 9-cycle is the smallest example for k=3.

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.

Back to Graph Coloring Problems homepage

Last modified February 15, 1999 Bjarne Toft and Tommy R. Jensen