Four-Coloring all but Three Vertices of a Toroidal Graph



Question: Does there exist for each surface S_g a constant M_g such that for every graph G embedded on S_g, all but M_g of the vertices of G can be 4-colored? In particular is M_1 = 3?

These questions originally appeared in [A]. [Note added by Dan Archdeacon: The first question was also submitted by Bojan Mohar who conjectured that the constants exist. He attributed the problem to Berman.]

A positive answer to the above must either use or reprove the Four Color Theorem. Carsten Thomassen (without using the 4CT) has shown that both questions have affirmative answers when the number of colors is five [T1,T2]. If G contains n vertices, then results of Hutchinson and Miller [HM] show that all but 26 squareroot(gn) of the vertices of G can be 4-colored.

Albertson and Hutchinson anticipated the preceding questions with one about alpha(G), the independence number of an embedded graph [AH]. Due to the historical accident of appearing prior to the 4CT, their question was originally formulated with the fraction 2/9.

Question: Is alpha(G) at least (n-M_g)/4 ?

References:

[A] M. O. Albertson, Open problem 2, The Theory and Applications of Graphs, ed. G. Chartrand et al., Wiley (1981) 609.

[AH] M. O. Albertson and J. P. Hutchinson, The maximum size of an independent set in a toroidal graph, Congressus Numerantium 14 (1975) 35-46.

[HM] J. P. Hutchinson and G. L. Miller, On deleting vertices to make a graph of positive genus planar, Discrete Algorithms and Complexity, ed. Johnson et al., Academic Press (1987) 81-98.

[T1] C. Thomassen, Five-coloring maps on surfaces, J. Combinatorial Theory B 59 (1993) 89-105.

[T2] C. Thomassen, Five-coloring graphs on the torus, J. Combinatorial Theory B 62 (1994) 11-33.


Submitted by: Mike Albertson, Dept.of Math., Smith College, Northampton, MA 01063 USA

Send comments to dan.archdeacon@uvm.edu and to albertson@smith.smith.edu

August, 1995