Publication details
Three-coloring triangle-free graphs on surfaces III. Graphs of girth five
| Authors | |
|---|---|
| Year of publication | 2020 |
| Type | Article in Periodical |
| Magazine / Source | Journal of Combinatorial Theory. Series B |
| MU Faculty or unit | |
| Citation | |
| Web | http://dx.doi.org/10.1016/j.jctb.2020.06.005 |
| Doi | http://dx.doi.org/10.1016/j.jctb.2020.06.005 |
| Keywords | Coloring; Triangle-free; Surfaces |
| Description | We show that the size of a 4-critical graph of girth at least five is bounded by a linear function of its genus. This strengthens the previous bound on the size of such graphs given by Thomassen. It also serves as the basic case for the description of the structure of 4-critical triangle-free graphs embedded in a fixed surface, presented in a future paper of this series. (C) 2020 Elsevier Inc. All rights reserved. |