Informace o publikaci
Three-coloring triangle-free graphs on surfaces III. Graphs of girth five
| Autoři | |
|---|---|
| Rok publikování | 2020 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Journal of Combinatorial Theory. Series B |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://dx.doi.org/10.1016/j.jctb.2020.06.005 |
| Doi | http://dx.doi.org/10.1016/j.jctb.2020.06.005 |
| Klíčová slova | Coloring; Triangle-free; Surfaces |
| Popis | 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. |