Problem 3.11: Acyclic Colorings


The answer to Problem 3.11 is NO!

N. Alon, B. Mohar, D.P. Sanders, and N. Robertson "Acyclic colouring of graphs on surfaces", Preprint 1994, proved with probabilistic arguments

a(Sg) ≥ g4/7 / 10(log g)1/7
where Sg denotes the sphere with g added handles.

They also proved by discharging arguments that

a(Sg) ≤ 200 g4/7 + 10,000.

Hence the asymptotic behaviour of a(Sg) has been determined almost exactly.

The interesting particular cases of a(torus) and a(projective plane) are still unanswered.

December 28, 1994. Tommy Jensen and Bjarne Toft.


The paper mentioned above has appeared:

N. Alon, B. Mohar and D.P. Sanders, On Acyclic Colorings of Graphs on Surfaces, Israel J. Math. 94 (1996), 273-283.

August 14, 1997. Tommy Jensen and Bjarne Toft.


Back to Overview menu
Back to Graph Coloring Problems homepage

Last modified August 14, 1997 Bjarne Toft