Three-coloring graphs embedded on surfaces with all faces even-sided. (English) Zbl 0828.05029
Every graph embedded on a surface of positive genus with every face bounded by an even number of edges can be 3-colored provided all noncontractible cycles in the graph are sufficiently long. The bound of three colors is the smallest possible for this type of result.
Reviewer: J.P.Hutchinson (St.Paul)
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C15 | Coloring of graphs and hypergraphs |
| 05C38 | Paths and cycles |
