Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 4 (2011) 153–164
Graphs with maximum degree 5 are acyclically
7-colorable∗
Alexandr V. Kostochka †
Department of Mathematics, University of Illinois, Urbana, IL 61801, USA
Sobolev Institute of Mathematics, Novosibirsk, 630090, Russia
Christopher Stocker
Department of Mathematics, University of Illinois, Urbana, IL 61801, USA
Received 12 May 2010, accepted 21 January 2011, published online 24 March 2011
Abstract
An acyclic coloring is a proper coloring with the additional property that the union of
any two color classes induces a forest. We show that every graph with maximum degree at
most 5 has an acyclic 7-coloring. We also show that every graph with maximum degree at
most r has an acyclic (1 + b (r+1)
2
4 c)-coloring.
Keywords: Acyclic coloring, maximum degree.
Math. Subj. Class.: 05C15, 05C35
1 Introduction
A proper coloring of the vertices of a graph G = (V,E) is an assignment of colors to the
vertices of the graph such that no two adjacent vertices receive the same color. A proper
coloring of a graph G is acyclic if the union of any two color classes induces a forest.
The acyclic chromatic number, a(G), is the smallest integer k such that G is acyclically
k-colorable. The notion of acyclic coloring was introduced in 1973 by Grünbaum [8] and
turned out to be interesting and closely connected to a number of other notions in graph
coloring. Several researchers felt the beauty of the subject and started working on problems
and conjectures posed by Grünbaum. Michael Albertson was among the enthusiasts and
wrote in total four papers on the topic [1, 2, 3, 4].
∗Dedicated to the memory of Michael Albertson
†Supported in part by NSF grants DMS-0650784 and DMS-0965587 and grant 09-01-00244-a of the Russian
Foundation for Basic Research.
E-mail addresses: kostochk@math.uiuc.edu (Alexandr V. Kostochka), stocker2@illinois.edu (Christopher
Stocker)
Copyright c© 2011 DMFA Slovenije
154 Ars Math. Contemp. 4 (2011) 153–164
In particular, Grünbaum studied a(r) – the maximum value of the acyclic chromatic
number over all graphs G with maximum degree at most r. He conjectured that for every
r, a(r) = r + 1 and proved that his conjecture holds for r ≤ 3. In 1979, Burstein [6]
proved the conjecture for r = 4. This result was proved independently by Kostochka [10].
It was also proved in [10] that for every k ≥ 3, the problem of deciding whether a graph
is acyclically k-colorable is NP-complete. It turned out that for large r, Grünbaum’s con-
jecture is incorrect in a strong sense. Albertson and Berman mentioned in [1] that Erdős
proved that a(r) = Ω(r4/3−) and conjectured that a(r) = o(r2). Alon, McDiarmid and
Reed [5] sharpened Erdős’ lower bound to a(r) ≥ c r4/3/(log r)1/3 and proved that
a(r) ≤ 50 r4/3. (1.1)
This established almost the order of the magnitude of a(r) for large r. Recently, the prob-
lem of estimating a(r) for small r was considered again.
Fertin and Raspaud [7] showed among other results that a(5) ≤ 9 and gave a linear-time
algorithm for acyclic 9-coloring of any graph with maximum degree 5. Furthermore, for
every fixed r ≥ 3, they gave a fast algorithm that uses at most r(r−1)/2 colors for acyclic
coloring of any graph with maximum degree r. Of course, for large r this is much worse
than the upper bound (1.1), but for r < 1000, it is better. Hocquard and Montassier [9]
showed that every 5-connected graph G with ∆(G) = 5 has an acyclic 8-coloring. Kotha-
palli, Varagani, Venkaiah, and Yadav [12] showed that a(5) ≤ 8. Kothapalli, Satish, and
Venkaiah [11] proved that every graph with maximum degree r is acyclically colorable
with at most 1 + r(3r + 4)/8 colors. This is better than the bound r(r − 1)/2 in [7] for
r ≥ 8. The main result of this paper is
Theorem 1.1. Every graph with maximum degree 5 has an acyclic 7-coloring, i.e., a(5) ≤
7.
We do not know whether a(5) is 7 or 6, and do not have a strong opinion about it.
Our proof is different from that in [7, 9, 12] and heavily uses the ideas of Burstein [6]:
he started from an uncolored graph G with maximum degree 4 and colored step by step
more and more vertices (with some recolorings) so that each of partial acyclic 5-colorings
of G had additional good properties that enabled him to extend the coloring further. The
proof yields a linear-time algorithm for acyclic coloring with at most 7 colors of any graph
with maximum degree 5. Using this approach we also show that for every fixed r ≥ 6,
there exists a linear-time algorithm giving an acyclic coloring of any graph with maximum
degree r with at most 1 + b (r+1)
2
4 c colors. This is better than the bounds in [7] and [11]
cited above for every r ≥ 6.
In the next section we introduce notation, prove two small lemmas and state the main
lemma. In Section 3 we prove Theorem 1.1 modulo the main lemma. In Section 4 we derive
linear-time algorithms for acyclic coloring of graphs with bounded maximum degree. In
the last section we give the proof of the main lemma.
2 Preliminaries
Let G be a graph. A partial coloring of G is a coloring of some subset of the vertices of
G. A partial acyclic coloring is then a proper partial coloring of G containing no bicolored
cycles.
A. V. Kostochka and C. Stocker: Graphs with maximum degree 5 are acyclically 7-colorable 155
Given a partial coloring f of G, a vertex v is
(a) rainbow if all colored neighbors of v have distinct colors;
(b) almost rainbow if there is a color c such that exactly two neighbors of v are colored
with c and all other colored neighbors of v have distinct colors;
(c) admissible if it is either rainbow or almost rainbow;
(d) defective if v is an uncolored almost rainbow vertex such that at least one of the two of
its neighbors receiving the same color is admissible.
A partial acyclic coloring f of a graph G is rainbow if f is a partial acyclic coloring of
G such that every uncolored vertex is rainbow.
A partial acyclic coloring f of a graph G is admissible if either f is rainbow or one
vertex is defective and all other uncolored vertices are rainbow. In these terms, a color-
ing is rainbow if it is admissible and has no defective vertices. Note that both, rainbow
and admissible colorings are partial acyclic colorings where additional restrictions are put
only on uncolored vertices. The advantage of using admissible colorings is that they pro-
vide a stronger induction condition that places additional restrictions only on coloring of
neighbors of uncolored vertices. So, the fewer uncolored vertices remain, the weaker these
additional restrictions are.
All colorings in this section will be from the set {1, 2, . . . , 7}.
Lemma 2.1. Let v be a vertex of degree 4 in a graph G with ∆(G) ≤ 5. Let f be an
admissible (respectively, rainbow) coloring in which v is colored with color c1, each of the
neighbors of v is colored, and exactly 3 colors appear on the neighbors of v. If at least
one of the two neighbors of v receiving the same color and one of the other two neighbors
of v each have a second (i.e., distinct from v) neighbor with color c1, then we can recolor
v and at most one of its neighbors so that the coloring remains admissible (respectively,
rainbow). In particular, the new partial acyclic coloring has no new defective vertices.
Moreover, if we need to recolor a vertex other than v, then we may choose a vertex with 5
colored neighbors and recolor it with a color incident to v in f .
Proof. Let N(v) = {z1, z2, z3, z4}, f(z1) = f(z2) = c2, f(z3) = c3, f(z4) = c4. Let z2
and z3 be the neighbors of v with colors c2, and c3 that are also adjacent to another vertex
of color c1. We may assume that z2 is adjacent to a vertex of color c5, since otherwise
when we recolor v with c5, no bicolored cycles appear and the coloring remains admissible
(respectively, rainbow). Similarly, we may assume that z2 is adjacent to vertices of colors
c6 and c7. Then we may recolor z2 with c3 and repeat the above argument to get that z3 also
is adjacent to vertices with colors c5, c6, and c7. In this case, we may change the original
coloring by recoloring z3 with c2 and v with c3. So, in this case only v and z3 change
colors. Note that either only v changes its color, or z2 receives color c3, or z3 receives
color c2.
For partial colorings f and f ′ of a graph G, we say that f ′ is larger than f if it colors
more vertices.
Lemma 2.2. Let v be a vertex of degree 4 in a graphG with ∆(G) ≤ 5. Let f be a rainbow
coloring in which v is colored with color c1, the neighbors z1, z2, and z3 of v receive the
distinct colors c2, c3, and c4, the neighbor z4 of v is an uncolored rainbow vertex. Then
either G has a rainbow coloring f1 that colors the same vertices and differs from f only
at v, or G has a rainbow coloring f ′ larger than f . Moreover, if the former does not hold,
156 Ars Math. Contemp. 4 (2011) 153–164
then z4 has degree 5 and exactly one uncolored neighbor, say z4,4, and we can choose the
larger coloring f ′ so that all the following are true:
1. Every vertex colored in f is still colored.
2. Vertex z4 is colored.
3. The only uncolored vertex apart from z4 that may get colored is z4,4, and it does only
if it has neighbors of colors c1, c2, c3, and c4.
4. Apart from v, only one vertex w may change its color, and if it does, then (a) w is a
neighbor of z4, (b)w has four colored neighbors, (c) it changes a color in {c5, c6, c7}
to another color in {c5, c6, c7}, and (d) z4 gets the former color of w. In particular,
v is admissible in f ′.
Proof. Let v, z1, z2, z3, and v4 be as in the hypothesis. We may assume that z4 is adjacent
to a vertex z4,1 of color c5: otherwise, since v4 is rainbow, when we recolor v with c5,
the new coloring will be rainbow. Similarly, we may assume that z4 is adjacent to vertices
z4,2, and z4,3 of colors c6 and c7. If z4 has no other neighbors, then we can recolor v
with c5 and color z4 with c1. So, assume that z4 has the fifth neighbor, z4,4. If z4,4 is
colored, then f(z4,4) ∈ {c2, c3, c4}, since z4 is rainbow. In this case, we let f ′(z4) = c1
and f ′(v) = c5. So, we may assume that z4,4 is not colored. If z4,4 has no neighbor of
color c2, then coloring z4 with c2 leaves the coloring rainbow and makes it larger than f .
Thus, we may assume that z4,4 has a neighbor of color c2 and similarly neighbors of colors
c3 and c4. If z4,4 has no neighbor of color c1, then we let f ′(z4) = c1 and f ′(v) = c5. So,
let z4,4 have such a neighbor.
If z4,1 has no neighbor of color c2, then by coloring z4 with c2 and z4,4 with c5, we
get a rainbow coloring larger than f . So, we may assume (by symmetry) that z4,1 has
neighbors of colors c2, c3, c4. If z4,1 has no neighbor of color c1, then we let f ′(z4) = c1,
f ′(z4,4) = c5, and f ′(v) = c6. Finally, if z4,1 also has a neighbor of color c1, then we let
f ′(z4,1) = c6 and f ′(z4) = c5.
The next lemma is our main lemma. We will use it in the next section and prove in
Section 5.
Lemma 2.3. Let f be an admissible partial coloring of a 5-regular graph G. Then G has
a rainbow coloring f ′ that colors at least as many vertices as f .
3 Proof the the Theorem
For convenience, we restate Theorem 1.1.
Theorem. Every graph with maximum degree 5 has an acyclic 7-coloring.
Proof. Let G be such a graph. If G is not 5-regular, form G′ from two disjoint copies
of G by adding for each v ∈ V (G) of degree less than 5 an edge between the copies of
v. Repeating this process at most five times gives a 5-regular graph G∗ containing G as a
subgraph. Since an acyclic 7-coloring of G∗ yields an acyclic 7-coloring of its subgraph
G, we may assume that G is 5-regular.
Let f be an admissible coloring of G from the set {1, 2, . . . , 7} with the most colored
vertices. By Lemma 2.3, we may assume that f is rainbow.
A. V. Kostochka and C. Stocker: Graphs with maximum degree 5 are acyclically 7-colorable 157
Let H be the subgraph of G induced by the vertices left uncolored by f . Let x be a
vertex of minimum degree in H . We consider several cases according to the degree dH(x).
Case 1: dH(x) = 0. Since f is rainbow, any color in {1, 2, . . . , 7}− f(NG(x)) can be
used to color x contradicting the maximality of f .
Case 2: dH(x) = 1. Since f is rainbow, we may assume that x is adjacent to vertices
of colors 1, 2, 3, and 4. Let y be the uncolored neighbor of x. Since y is rainbow, coloring
x with 5 gives either a rainbow coloring or an admissible coloring with the defective vertex
y having the admissible neighbor x, a contradiction to the maximality of f .
Case 3: dH(x) = 2. We may assume that x is adjacent to vertices with colors 1, 2, 3,
and two uncolored vertices y1 and y2. Since in our case y1 is adjacent to at most 3 colored
vertices, some color c ∈ {4, 5, 6, 7} does not appear on the neighbors of y1. Coloring x
with c then yields either a rainbow coloring, or an admissible coloring with defective vertex
y2 and its admissible neighbor x, a contradiction to the maximality of f .
Case 4: dH(x) = 3. We may assume that x is adjacent to vertices of colors 1 and 2.
By the choice of x, each uncolored vertex of G has at most 2 colored neighbors. Since
the three uncolored neighbors of x have at most 6 colored neighbors in total, some color
c ∈ {3, 4, 5, 6, 7} is present at most once among these 6 neighbors. Then coloring x with c
again yields an admissible coloring, a contradiction to the maximality of f .
Case 5: dH(x) ≥ 4. Since each vertex of G has at most one colored neighbor, at
most 5 colors are used in the second neighborhood of x. Hence x may be colored to give a
rainbow coloring with more colored vertices.
We conclude that H is empty and that f is an acyclic 5-coloring of G.
4 Algorithms
Theorem 4.1. There exists a linear time algorithm for finding an acyclic 7-coloring of a
graph with maximum degree 5.
Proof. The proof of the Theorem 1.1, along with Lemmas 2.1–2.3 gives an algorithm.
In order to control the efficiency of the algorithm we make the following modification:
whenever the proof checks whether a vertex v is in a two-colored cycle, we check only
for such a cycle of length at most 12, and if we do not find such a short cycle, then check
whether two bicolored paths of length 6 leave v. This is enough, since the existence of such
paths already makes the proofs of Theorem 1.1 and all the lemmas work. So, we need only
to consider a bounded (at most 56) number of vertices around our vertex. It then suffices
to compute the running time of this algorithm. Let n be the number of vertices in G. The
process of creating a 5-regular graph takes O(n) time since we apply this process at most
5 times, each time on at most 25n vertices, each of degree at most 5. We may now assume
that G is a 5-regular graph. We then create and maintain 6 databases Dj , j = 0, 1, . . . , 5
(say doubly linked lists), each for the set of vertices with degree j in the current H . At
the beginning, all vertices are in D5, and it is possible to update the databases in a constant
amount of time each time a vertex gains or loses a colored neighbor. Since there are at most
25n possible searches for a vertex with the minimum number of uncolored neighbors, all
the searches and updates will take O(n) time. Note that the processes of Lemma 2.1 and
Lemma 2.2 also take a constant amount of time to complete. Observe that each of the cases
in Lemma 2.3 either finds a rainbow coloring, or finds an admissible coloring with more
colored vertices, or reduces to a previous case in an amount of time bounded by a constant.
Also when Lemma 2.3 processes a defective vertex, it yields either a rainbow coloring, or
158 Ars Math. Contemp. 4 (2011) 153–164
a larger admissible coloring and the next defective vertex in a constant time. Finally, since
we start from an uncolored graph and color each additional vertex in a constant time, the
implied algorithm colors all vertices in O(n) time.
For a partial coloring f of a graph G and a vertex v ∈ V (G), we say that u ∈ V (G) is
f -visible from v, if either vu ∈ E(G) or v and u have a common uncolored neighbor.
Theorem 4.2. For every fixed r, there exists a linear (in n) algorithm finding an acyclic
coloring for any n-vertex graph G with maximum degree r using at most 1 + b (1+r)
2
4 c
colors.
Proof. We start from the partial coloring f0 that has no colored vertices, and for i =
1, . . . , n at Step i obtain a rainbow partial acyclic coloring fi from fi−1 by coloring one
more vertex (without recoloring). The algorithm proceeds as follows: at Step i, choose an
uncolored vertex vi with the most colored neighbors. Greedily color vi with a color αi in
C := {1, . . . , 1+b (1+r)
2
4 c} that is distinct from the colors of all vertices fi−1-visible from
vi. We claim that we always can find such αi in C.
Suppose that at Step i, vi has exactly k colored neighbors. Then it has at most r−k un-
colored neighbors, and each of these uncolored neighbors has at most k colored neighbors.
So, the total number of vertices fi−1-visible from vi is at most
k + (r − k)k = k(r + 1− k) ≤
⌊
(r + 1)2
4
⌋
= |C| − 1,
and we can find a suitable color αi for vi.
It now suffices to show that for each i, the coloring fi is rainbow and acyclic. For f0,
this is obvious. Assume now that fi−1 is rainbow and acyclic. Since vi is rainbow in fi−1,
coloring it with αi does not create bicolored cycles. Thus, fi is acyclic. Also since αi is
distinct from the colors of all vertices fi−1-visible from vi, fi is rainbow.
For the runtime, note that at Step i the algorithm considers only vi and vertices at
distance at most 2 from vi. As in the proof of Theorem 4.1, it is sufficient to maintain r+ 1
databases each containing all vertices with a given number of colored neighbors. This
allows a constant time search for a vertex with the greatest number of colored neighbors.
Moving a vertex as its number of colored neighbors changes takes a constant amount of
time. Choosing and coloring vi together with updating the databases then takes O(r2)
time. Hence the running time of the algorithm is at most crn, where cr depends on r.
5 Proof of Lemma 2.3
We will prove that under the conditions of the lemma, either its conclusion holds or there is
an admissible coloring f ′′ larger than f . SinceG is finite, repeating the argument eventually
yields either an acyclic coloring of the whole G or a rainbow coloring. In both cases we do
not have defective vertices.
Let H be the subgraph of G induced by the uncolored vertices. Let x be the sole
defective vertex under f and let y1, y2, . . . , y5 be its neighbors. By the definition of a
defective vertex, x has two neighbors of the same color. We will assume that f(y1) =
f(y2) = 1 and that y1 is admissible. When more then two neighbors of x are colored, we
assume for i = 3, 4, 5 that if yi is colored, then f(yi) = i − 1. Also for i = 1, . . . , 5, the
four neighbors of yi distinct from x will be denoted by yi,1, . . . , yi,4 (some vertices will
A. V. Kostochka and C. Stocker: Graphs with maximum degree 5 are acyclically 7-colorable 159
have more than one name, since they may be adjacent to more than one yi). We consider
several cases depending on dH(x).
Case 1: dH(x) = 0. First we try to color x with colors 5, 6, and 7. If this is not
allowed, then for j = 5, 6, 7, G has a 1, j-colored y1, y2-path. This forces that both of y1
and y2 have neighbors with colors 5, 6, and 7, each of which is adjacent to another vertex
of color 1. In particular, both y1 and y2 are admissible. For i = 1, 2 and j = 1, 2, 3, we
suppose that f(yi,j) = j + 4 and yi,j is adjacent to another vertex of color 1.
Case 1.1: For some i ∈ {1, 2}, yi,4 is colored and f(yi,4) /∈ {5, 6, 7}. By symmetry,
we may assume that i = 1 and f(y1,4) = 2. Recolor y1 with 3 and call the new admissible
coloring f ′. If we can now recolor y2 so that the resulting coloring f ′′ is rainbow on
G − xy2 − xy1 or the only defective vertex in f ′′ on G − xy2 − xy1 is y2,4, then we do
this recoloring and color x with 1. Since y1 and y2 have no neighbors of color 1 apart
from x, we obtained an admissible coloring of G larger than f . If we cannot recolor y2
to get such a coloring, then y2,4 is colored with a color c ∈ {5, 6, 7}. Moreover, in this
case by Lemma 2.1 applied to y2 in coloring f ′ of G − xy2 − xy1, we can change the
colors of only y2 and some y ∈ {y2,1, y2,2, y2,3, y2,4} to get an admissible coloring f1 of
G − xy2 − xy1. Moreover, by Lemma 2.1, f1(y) ∈ {5, 6, 7}. Then by coloring x with 1
we obtain a rainbow coloring of G, as above.
Case 1.2: y1,4 is not colored. By Lemma 2.2 for vertex y1 in G− xy1, either G− xy1
has a rainbow coloring f ′ that differs from f only at y1 (in which case by symmetry, we
may assume that f ′(y1) = 3 and proceed further exactly as in Case 1.1), or G− xy1 has a
larger rainbow coloring f ′ satisfying statements 1)–4) of Lemma 2.2. In particular, by 4),
none of y2, y3, y4, y5 changes its color and y1 remains admissible. This finishes Case 1.2.
By the symmetry between y1 and y2, the remaining subcase is the following.
Case 1.3: f(y1,4) = 5 and f(y2,4) = c ∈ {5, 6, 7}. By Lemma 2.1 applied to y1
in G − xy1, we can recolor y1 and at most one other vertex (a neighbor of y1) to obtain
another admissible coloring f ′. If f ′(y1) ∈ {5, 6, 7}, then f ′ is a rainbow coloring, as
claimed. So, we may assume that f ′(y1) = c1 ∈ {2, 3, 4}. If all the colors 5, 6, 7 are
present on neighbors of y2, then again by Lemma 2.1 (applied now to y2 in coloring f ′ of
G − xy2), G has an admissible coloring f ′′ that differs from f ′ only at y2 and maybe at
one neighbor of y2. Then coloring x with 1 we get a rainbow coloring. So, some color
in {5, 6, 7} is not present in f ′(N(y2)). By Lemma 2.1, this may happen only if y1,1 is a
common neighbor of y1 and y2, and c = f(y2,4) 6= 5. In particular, in this case, y1,1 has
neighbors of colors 1 (they are y1 and y2), 2, 3, and 4. Since c 6= 5, we may assume that
c = 6. By the symmetry between y1 and y2, we conclude that, in f , vertex y2,2 also is a
common neighbor of y1 and y2 and has neighbors of colors 1 (they are y1 and y2), 2, 3, and
4. Returning to coloring f ′, we see that y2 has no neighbors of color 5, and its neighbors
y1,1 (formerly of color 5) and y2,2 (by the previous sentence) also have no neighbors of
color 5. So, recoloring y2 with 5 yields an admissible coloring of G. Now coloring x with
1 creates a larger rainbow coloring.
Case 2: dH(x) = 1. We first try to color x with 4. If no bicolored cycle is formed,
then either we have a rainbow coloring or an admissible coloring with defective vertex
y5 and an admissible neighbor x. Hence we may assume that coloring x with 4 creates
a bicolored cycle. This then gives each of y1 and y2 a neighbor of color 4. A similar
argument gives each of y1 and y2 a neighbor of color 5, 6, and 7, i.e., both y1 and y2
are rainbow. Recoloring y1 with color 2 allows us to repeat the argument at y3. Then
y3 also has neighbors of each of the colors 4, 5, 6, and 7. If y5 has no neighbor of color
160 Ars Math. Contemp. 4 (2011) 153–164
2, then recoloring (in the original coloring f ) y3 with 1, and coloring x with 2 yields a
rainbow coloring. So, by the symmetry between colors 1, 2, and 3, we may assume that for
i ∈ {1, 2, 3}, f(y5,i) = i. Since y5 is rainbow, by the symmetry between colors 4, 5, 6,
and 7, we may assume that either f(y5,4) = 4, or y5,4 is not colored. In both cases, recolor
(in the original coloring f ) y3 with 1, color x with 2 and y5 with 5. We get an admissible
coloring larger than f , where only y5,4 may be defective.
Case 3: dH(x) = 3. If one of the uncolored neighbors y3, y4, y5 (say, y3) of x has 4
colored neighbors, then we may color y3 with some c /∈ f(N(y3)) ∪ {1} and thus create
an admissible coloring larger than f . Hence we may assume that each of y3, y4, and y5 has
at most 3 colored neighbors.
Case 3.1: One of y1 and y2 has three neighbors of different colors such that each of
these neighbors has another neighbor of color 1. Suppose for example that for j = 1, 2, 3,
f(y1,j) = 1 + j and y1,j has another neighbor of color 1. If y1 has a fourth color, say c,
in its neighborhood, then we recolor y1 with a color c′ /∈ {1, c, 5, 6, 7} and get a rainbow
coloring of G. Suppose now that color c ∈ {5, 6, 7} appears twice on N(y1). Then by
Lemma 2.1 applied to y1 in G− xy1, we can change the color of y1 and at most one other
vertex that is a neighbor of y1 not adjacent to uncolored vertices to get another rainbow
coloring of G − xy1. Then this coloring will also be a rainbow coloring of G. Finally,
suppose that y1 has an uncolored neighbor y1,4. Applying Lemma 2.2 to y1 in G − xy1
we either recolor only y1 and get a rainbow coloring of G (finishing the case), or obtain
a rainbow coloring f ′ of G − xy1 larger than f satisfying the conclusions of the lemma.
Since each of y3, y4 and y5 has at least two neighbors left uncolored by f , none of them
may play role of z4 or z4,4 in Lemma 2.2 when they get colored. Then f ′ is an admissible
coloring of G where only x could be a defective vertex with admissible neighbor v. This
proves Case 3.1.
Let T be the set of colors c such that more than one of the vertices y3, y4 and y5 has a
neighbor of color c. Since y3, y4 and y5 have in total at most 9 colored neighbors, |T | ≤ 4.
Case 3.2: |T | ≤ 3. By symmetry, we may assume that T ⊆ {2, 3, 4}. If coloring x
with c ∈ {5, 6, 7} does not create a bicolored cycle, then it will yield an admissible coloring
larger than f . So, we may assume that each of y1 and y2 has in its neighborhood vertices
of colors 5, 6, and 7, each of which is adjacent to another vertex of color 1. So, we have
Case 3.1.
Case 3.3: |T | = 4. Let T = {2, 3, 4, 5}. As in Case 3.1, we may assume that each of
y1 and y2 is adjacent to vertices of colors 6 and 7, each of which have another neighbor of
color 1.
Let y3 have exactly 3 colored neighbors labeled y3,1, y3,2, y3,3 with colors 2, 3, 4. Let
y3,4 be the uncolored neighbor of y3. Then if y3,4 has no neighbor of color 5, we may color
y3 with 5 to get a new admissible coloring. Hence y3,4 is adjacent to a vertex of color 5.
Similarly, y3,4 has neighbors of color 6 and 7. By symmetry, we may assume that a vertex
of color 2 is adjacent to at most one of y4 and y5.
Case 3.3.1: y3,4 has no neighbor of color 1. We try to color y3 with 1 and x with 2.
If this does not produce a new admissible coloring, then one of y1 or y2, say y1, has a
neighbor of color 2 that is adjacent to another vertex of color 1. So, we again get Case 3.1.
Case 3.3.2: y3,4 has a neighbor of color 1. If y3,1 has no neighbor of color 1, then we
again try to color y3 with 1 and x with 2, but also color y3,4 with 2. Then we simply repeat
the argument of Case 3.3.1. So, suppose that y3,1 has a neighbor of color 1. If y3,1 has no
neighbor of some color α ∈ {5, 6, 7}, then we color y3,4 with 2 and y3 with α. Thus y3,1
A. V. Kostochka and C. Stocker: Graphs with maximum degree 5 are acyclically 7-colorable 161
1 1
2
3 4 5
y4,1 y4,2 y4,3 y4,4
3 4 5
y5,1 y5,2 y5,3 y5,4
y2 y1
x
y3 y4 y5
6 6 7 7
Case 4.3.
1 1
2
5 5 6 76 6 6 7
3 4 5
6 7
3 4 5
6 7
y2 y1
x
y3 y4 y5
Case 4.3.4.3.
Figure 1: Cases 4.3 and 4.3.4.3 from the proof of Lemma 2.3.
has neighbors of colors 1, 5, 6, 7. Then we recolor y3,1 with 3 and color y3 with 2.
Case 4: dH(x) = 2. As at the beginning of Case 3, we conclude that each of the
uncolored vertices y4 and y5 has at least one uncolored neighbor besides x.
Let B be the set of colors appearing in the neighborhoods of both, y4 and y5. By the
previous paragraph, |B| ≤ 3.
Case 4.1: |B| ≤ 1. We may assume that {4, 5, 6, 7} ∩ B = ∅. Try to color x with
4. By the definition of B, either a two-colored cycle appears, or we get a new admissible
coloring larger than f . Hence we may assume that coloring x with 4 creates a bicolored
cycle. Since this cycle necessarily goes through y1, y1 is adjacent to a vertex with color
4. Similarly, y1 is adjacent to vertices with colors 5, 6, and 7. Then recoloring y1 with 3
yields a rainbow coloring of G.
Case 4.2: |B| = 2. If 1 ∈ B or 2 ∈ B, then the argument of Case 4.1 holds. Assume
that B = {3, 4}. Similarly to Case 4.1, we may assume that for i = 1, 2 and j = 1, 2, 3,
yi is adjacent to a vertex yi,j of color j + 4 that is adjacent to another vertex of color 1 (in
particular, y1 and y2 may have a common neighbor of color j + 4).
If y1 is rainbow, then uncoloring y1 and coloring x with 7 gives Case 1 or Case 2. Thus
we may assume that y1 and (by symmetry) y2 are not rainbow. So, we may assume that
for i = 1, 2, the fourth neighbor yi,4 of yi distinct from x has color ci ∈ {5, 6, 7}. By
symmetry, we may assume that c1 = 5. Similarly to Case 1.3, by Lemma 2.1 applied to
y1 in G− xy1, we can recolor y1 and at most one other vertex (a neighbor of y1) to obtain
another rainbow coloring f ′ of G − xy1. If f ′(y1) ∈ {3, 4, 5, 6, 7}, then f ′ is a rainbow
coloring of G, as claimed. So, we may assume that f ′(y1) = 2. Now practically repeating
the argument of Case 1.3, we find a promised coloring.
Case 4.3: |B| = 3 (see Figure 1). If 2 ∈ B, then we can repeat the argument of Case
4.2 for B′ = B − {2}. Hence we may assume that B ⊆ {1, 3, 4, 5, 6, 7}.
Case 4.3.0: 1 ∈ B. Let B = {1, 3, 4}. Then some color in {5, 6, 7}, say 7, is not
present on N(y4) ∪ N(y5). Again, we may assume that for i = 1, 2 and j = 1, 2, 3, yi is
162 Ars Math. Contemp. 4 (2011) 153–164
adjacent to a vertex yi,j of color j + 4 that is adjacent to another vertex of color 1. If y1 is
rainbow, then we may uncolor y1 and color x with 7 to get Case 1 or Case 2. Suppose now
that y1 and y2 are not rainbow. By Lemma 2.1 applied to y1 in G− xy1, we can recolor y1
and at most one other vertex (a neighbor of y1) to obtain another admissible coloring f ′.
If f ′(y1) ∈ {3, 4, 5, 6, 7}, then f ′ is a rainbow coloring, as claimed. So, we may assume
that f ′(y1) = 2. But then we can use the argument of Case 4.2 with the roles of y3 and y2
switched. This proves Case 4.3.0.
So, from now on, B = {3, 4, 5}. For i = 4, 5 and j = 1, 2, 3, let yi,j be the neighbor of
yi of color j + 2. We write the neighbor, since y4 and y5 are rainbow. As observed at the
beginning of Case 4, y4 and y5 each have another uncolored neighbor, call them y4,4 and
y5,4. In particular, y4 and y5 have no neighbors colored with 6 or 7. If x can be colored with
either of 6 or 7 without creating a two-colored cycle, then we obtain a rainbow coloring.
Hence we assume that for i = 1, 2 and j = 1, 2, f(yi,j) = j + 5 and yi,j has a neighbor of
color 1 distinct from yi.
Case 4.3.1: One of y1 or y2, say y1, is rainbow. If y4,4 has no neighbor of color
c ∈ {6, 7}, then we can color y4 with c, a contradiction to the maximality of f . If y4,4 has
no neighbor of color c′ ∈ {1, 2}, then by uncoloring y1 and coloring y4 with c′ and x with
6, we obtain an admissible coloring larger than f . So, f(N(y4,4)) = {1, 2, 6, 7}. Then we
may color y4,4 with 3 and uncolor y1 to get a new admissible coloring as large as f with
one defective vertex y4, for which Case 2 holds. This finishes Case 4.3.1.
So, below y1 and y2 are not rainbow and hence each of them is adjacent to at least three
colored vertices.
Case 4.3.2: One of y1 or y2, say y1, is adjacent to an uncolored vertex y1,4 6= x. We
may assume that f(y1,1) = f(y1,2) = 6 and f(y1,3) = 7. First, we try to color x with 7
and y1 with 3. Since the new coloring has at most one defective vertex, we may assume
that a two-colored cycle is created. Hence each of y1,1 and y1,2 is adjacent to a vertex of
color 3. The same argument gives these vertices neighbors of colors 4 and 5. Recall that
one of y1,1 and y1,2, say y1,1, has another neighbor of color 1. Then recoloring y1,1 with 2
gives an admissible coloring in which y1 is rainbow. Hence Case 4.3.1 applies to this new
coloring.
So, from now on each of y1 and y2 has 4 colored neighbors. Since y1 is admissible we
may assume w.l.o.g. that y1 is adjacent either to the colors 5, 6, 6, 7 or the colors 5, 5, 6, 7.
Case 4.3.3: y1 has one neighbor of color 5 and three neighbors with colors 6 or 7. We
may assume that f(y1,1) = 5, f(y1,2) = f(y1,3) = 6, and f(y1,4) = 7. If coloring y1
with 3 or 4 yields an admissible coloring, then we are done; so we may assume that a two-
colored cycle is formed in each case. It follows that each of y1,2 and y1,3 has neighbors
colored with 3 and 4. By the symmetry between y1,2 and y1,3, we may assume that y1,3
has a neighbor of color 1 other than y1. If y1,3 is almost rainbow, then we can uncolor it,
recolor y1 with 3, and color x with 7: this will give an admissible coloring with the same
number of colored vertices as in f , and the only defective vertex y1,3. Then either Case 1
or Case 2 applies to this new coloring. Hence we may assume that y1,3 has two neighbors
other than y1 that receive the same color. Then since y1,3 has no neighbor of color 2, y1
may now be recolored with color 2 without creating a bicolored cycle. Repeating the above
argument we derive that y1,2 has neighbors of colors 2, 3, and 4, and one of these colors
appears twice on N(y1,2)− y1. By Lemma 2.1 applied to y1,3 in the graph G− y1,3y1 for
the original coloring, we can change its color and the color of at most one other vertex (that
is a neighbor of y1,3, all of whose neighbors are colored) to get an admissible coloring of
A. V. Kostochka and C. Stocker: Graphs with maximum degree 5 are acyclically 7-colorable 163
G − y1,3y1. Since y2 and y3 are adjacent to the uncolored vertex x, their colors are not
changed. If y1,3 receives color 1, then we recolor y1 with 3 and get a rainbow coloring of
G. If y1,3 receives a color other than 1, then we color x with 6 and again get a rainbow
coloring of G.
Case 4.3.4: y1 has two neighbors of color 5 (see Figure 1). We may assume that
f(y1,1) = f(y1,2) = 5, f(y1,3) = 6, and f(y1,4) = 7. If y1 can be recolored with either
3 or 4, this would give a rainbow coloring f ′. Hence we assume that both of y1,1 and y1,2
are adjacent to vertices with colors 3 and 4.
Case 4.3.4.1: One of y1,1 or y1,2, say y1,1, is rainbow. Then uncoloring y1,1 and
coloring y1 with 3 and x with 7 yields either a rainbow coloring f ′ or a new admissible
coloring (with the same number of colored vertices) with the defective vertex y1,1 and
admissible colored neighbor y1. In the former case, we are done. In the latter, if one of the
previous cases occurs, then we are done again. So, we may assume that Case 4.3.4 occurs.
By the symmetry between colors 3 and 4, we may assume that apart from y1, vertex y1,1
has a neighbor of color 3, a neighbor of color 4, and two uncolored neighbors, say z1 and
z2, each of whose has another uncolored neighbor and 3 colored neighbors. Moreover, the
same 3 colors appear on the neighborhoods of z1 and z2, and since Case 4.3.4 holds, by
the symmetry between colors 6 and 7, both of them are among these 3 colors. Then either
coloring y1,1 with 1 yields a rainbow coloring or coloring y1,1 with 2 does.
Case 4.3.4.2: Each of y1,1 and y1,2 has a neighbor of color 2 that has another neighbor
of color 5. Since y1,1 is not rainbow, the fourth neighbor of y1,1 has color c ∈ {2, 3, 4}.
Since y1 cannot be recolored with 3 or 4, some neighbor, say r, of y1,1 of color c has
another neighbor of color 5. If in the graph G− y1y1,1, y1,1 can be recolored with 1, then
we may recolor y1 with 3 and get a rainbow coloring of G. If y1,1 can be recolored with
either of 6 or 7, then we have Case 4.3.3. To disallow coloring y1,1 with 1, 6, and 7, r must
be adjacent to vertices with each of these colors. By the symmetry between colors 3 and
4, we assume that f(r) 6= 4. If the neighbor r′ of y1,1 with f(r′) = 4 has no neighbor of
color c′ ∈ {6, 7}, then we recolor r with 4 and y1,1 with c′ thus getting Case 4.3.3. If r′
has no neighbor of color 1, then we recolor r with 4, y1,1 with 1, and y1 with 3 obtaining a
rainbow coloring. Finally if f(N(r′)− y1,1) = {1, 5, 6, 7}, then we recolor r′ with 3, y1,1
with 4, and y1 with 3.
The last subcase is:
Case 4.3.4.3: y1,1 has no neighbor of color 2 that has another neighbor of color 5.
Then recoloring y1 with 2 creates another admissible coloring f ′. We may then repeat our
previous argument with y3 playing the role of y2 to conclude that y3 has neighbors of color
6 and 7. If y3 is admissible, then repeating the above argument we conclude that y3 may be
recolored with color 1 in the original coloring f . Then after this recoloring, by coloring x
with 2 we get a rainbow coloring. Also, if y2 is admissible in f , then we may recolor both
of y1 and y2 with 2 and color x with 1 to get a rainbow coloring. Hence we may assume
that all the neighbors of y2 and y3 apart from x are colored with 6 or 7. Recall that for
i = 4, 5 and j = 1, 2, 3, f(yi,j) = j + 2 and yi,4 is uncolored. If for some i ∈ {4, 5}, yi,4
has no neighbor of color c ∈ {6, 7}, then we can color yi with c and get a better admissible
coloring. Since none of y1, y2, or y3 has a neighbor with color 3, if y4,4 has no neighbor of
color 1 or y5,4 has no neighbor of color 2, then by coloring y4 with 1, y5 with 2 and x with
3 creates an admissible coloring with more colored vertices. By the symmetry between
colors 1 and 2, each of y4,4 and y5,4 has neighbors of colors 1, 2, 6, and 7.
If y4,1 does not have a neighbor of color c′ ∈ {1, 2, 6, 7}, then coloring y4,4 with 3, y4
164 Ars Math. Contemp. 4 (2011) 153–164
with c′ and x with 4 yields an admissible coloring. Otherwise, we recolor y4,1 with 4 and
color y4 with 3. This proves the lemma.
6 Acknowledgment
We thank the referees for the helpful comments.
References
[1] M. O. Albertson and D. M. Berman, The acyclic chromatic number, Congressus Numerantium,
No. XVII (1976), Utilitas Math., Winnipeg, Man., 51–69.
[2] M. O. Albertson and D. M. Berman, Every planar graph has an acyclic 7-coloring, Israel J.
Math. 28 (1977), 169–174.
[3] M. O. Albertson and D. M. Berman, An acyclic analogue to Heawood’s theorem, Glasgow
Math. J. 19 (1978), 163–166.
[4] M. O. Albertson, G. G. Chappell, H. A. Kierstead, A. Kündgen and R. Ramamurthi, Coloring
with no 2-colored P4’s, Electron. J. Combin. 11 (2004), R#26.
[5] N. Alon, C. McDiarmid and B. Reed, Acyclic coloring of graphs, Random Structures Algo-
rithms 2 (1991), 277–288.
[6] M. I. Burstein, Every 4-valent graph has an acyclic 5-coloring, Soobšč. Akad. Nauk Gruzin.
SSR 93 (1979), 21–24.
[7] G. Fertin and A. Raspaud, Acyclic coloring of graphs of maximum degree five: nine colors are
enough, Information Processing Letters 105 (2008), 65–72.
[8] B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math 14 (1973), 390–408.
[9] H. Hocquard, M. Montassier, Acyclic coloring of graphs with maximum degree five, http:
//hal.archives-ouvertes.fr/hal-00375166/en/.
[10] A. V. Kostochka, Upper bounds on the chromatic characteristics of graphs, PhD Thesis, Insti-
tute of Mathematics, Novosibirsk, 1978.
[11] K. Kothapalli, V. Satish and V. Ch. Venkaiah, Acyclic vertex coloring of graphs of maximum
degree ∆, Talk at 75th Annual conference of the Indian Math. Society, Kalasalingam Univ.,
Krishnakoil, December 2009.
[12] K. Kothapalli, S. Varagani, V. Ch. Venkaiah and K. Yadav, Acyclic Vertex Coloring of Graphs
of Maximum Degree 5, Proc. Int. Conf. on Graph Theory and its Applications, Amrita Vishwa
Vidyapeetham, Coimbatore, December, 2008.