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