The Library
Three-coloring triangle-free graphs on surfaces III. Graphs of girth five
Tools
Dvořák, Zdeněk, Král', Daniel and Thomas, Robin (2020) Three-coloring triangle-free graphs on surfaces III. Graphs of girth five. Journal of Combinatorial Theory, Series B, 145 . pp. 376-432. doi:10.1016/j.jctb.2020.06.005 ISSN 0095-8956.
|
PDF
WRAP-three-coloring-triangle-free-graphs-surfaces-III-Kral-2020.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (1181Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.jctb.2020.06.005
Abstract
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.
Item Type: | Journal Article | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
||||||||||||
Library of Congress Subject Headings (LCSH): | Graph theory, Combinatorial analysis, Computer science -- Mathematics | ||||||||||||
Journal or Publication Title: | Journal of Combinatorial Theory, Series B | ||||||||||||
Publisher: | Academic Press | ||||||||||||
ISSN: | 0095-8956 | ||||||||||||
Official Date: | November 2020 | ||||||||||||
Dates: |
|
||||||||||||
Volume: | 145 | ||||||||||||
Page Range: | pp. 376-432 | ||||||||||||
DOI: | 10.1016/j.jctb.2020.06.005 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||
Date of first compliant deposit: | 7 July 2020 | ||||||||||||
Date of first compliant Open Access: | 2 July 2021 | ||||||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year