The chromatic number of a graph of girth 5 on a fixed surface (Q1403910): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q190560 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Ioan Tomescu / rank | |||
Normal rank |
Revision as of 12:05, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The chromatic number of a graph of girth 5 on a fixed surface |
scientific article |
Statements
The chromatic number of a graph of girth 5 on a fixed surface (English)
0 references
20 August 2003
0 references
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.
0 references
4-color-critical graph
0 references
polynomial time
0 references