The chromatic number of a graph of girth 5 on a fixed surface (Q1403910): Difference between revisions

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.