Graph Coloring Problems

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

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.

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.

[1981] Krusenstjerna-Hafstrøm, U., and B. Toft, Special subdivisions of

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 45^{o}
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.