zbMATH — the first resource for mathematics

The chromatic number of a graph of girth 5 on a fixed surface. (English) Zbl 1020.05030
In this interesting paper it is proved that, for every surface \(S\) and every natural number \(k\), there exists a natural number \(f(S,k)\) such that the following holds: If \(G\) is a graph of girth 5 on \(S\), and \(H\) is a 3-colored subgraph with at most \(k\) vertices, then either the coloring of \(H\) can be extended to a 3-coloring of \(G\), or else there is a small obstruction containing \(H\), that is, a subgraph \(H'\) with at most \(f(S,k)\) vertices such that the coloring of \(H\) cannot be extended to a 3-coloring of \(H'\). In particular, there are only finitely many 4-color-critical graphs of girth 5 on \(S\), as a 4-color-critical graph of girth 5 on \(S\) has at most \(f(S,1)\) vertices. It follows that, if \(G\) is a graph of girth 5 on \(S\), and all noncontractible cycles in \(G\) have length greater than \(f(S,1)\), then \(G\) is 3-colorable. The result is best possible in the sense that there are infinitely many 4-color-critical graphs of girth 4 on \(S\), except when \(S\) is the sphere. As a consequence, it is deduced that the chromatic number of graphs of girth 5 on \(S\) can be found in polynomial time.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), Macmillan London · Zbl 1134.05001
[2] Fisk, S.; Mohar, B., Coloring graphs without short non-bounding cycles, J. combin. theory ser. B, 60, 268-276, (1994) · Zbl 0793.05058
[3] Gimbel, J.; Thomassen, C., Coloring graphs with fixed genus and girth, Trans. amer. math. soc., 349, 4555-4564, (1997) · Zbl 0884.05039
[4] Jensen, T.; Toft, B., Graph coloring problems, (1995), Wiley New York · Zbl 0855.05054
[5] Malnic̆, A.; Mohar, B., Generating locally cyclic triangulation of surfaces, J. combin. theory ser. B, 56, 147-164, (1992) · Zbl 0723.05053
[6] Mohar, B.; Thomassen, C., Graphs on surfaces, (2001), Johns Hopkins University Press Baltimore · Zbl 0979.05002
[7] Thomassen, C., Every planar graph is 5-choosable, J. combin. theory ser. B, 62, 180-181, (1994) · Zbl 0805.05023
[8] Thomassen, C., Grötzsch’s 3-color theorem and its counterpart for the torus and the projective plane, J. combin. theory ser. B, 62, 268-279, (1994) · Zbl 0817.05024
[9] Thomassen, C., 3-List-coloring planar graphs of girth 5, J. combin. theory ser. B, 64, 101-107, (1995) · Zbl 0822.05029
[10] Thomassen, C., Color-critical graphs on a fixed surface, J. combin. theory ser. B, 70, 67-100, (1997) · Zbl 0883.05051
[11] C. Thomassen, A short list color proof of Grötzsch’s theorem, J. Combin. Theory Ser. B, to appear.
[12] B. Walls, Coloring girth restricted graphs on surfaces, Ph.D. Thesis, Georgia Institute of Technology, 1999.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.