The Library
Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs
Tools
Dvořák, Zdeněk, Král', Daniel and Thomas, Robin (2021) Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs. Journal of Combinatorial Theory, Series B, 150 . pp. 270-304. doi:10.1016/j.jctb.2020.09.001 ISSN 0095-8956.
|
PDF
WRAP-Three-coloring-triangle-free-graphs-surfaces-Kral-2020.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (1028Kb) | Preview |
Official URL: https://doi.org/10.1016/j.jctb.2020.09.001
Abstract
Let G be a 4-critical graph with t triangles, embedded in a surface of genus g. Let c be the number of 4-cycles in G that do not bound a 2-cell face. We prove that for a fixed constant κ, thus generalizing and strengthening several known results. As a corollary, we prove that every triangle-free graph G embedded in a surface of genus g contains a set of vertices such that is 3-colorable.
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 coloring, Triangle, Sphere | ||||||||||||
Journal or Publication Title: | Journal of Combinatorial Theory, Series B | ||||||||||||
Publisher: | Academic Press | ||||||||||||
ISSN: | 0095-8956 | ||||||||||||
Official Date: | September 2021 | ||||||||||||
Dates: |
|
||||||||||||
Volume: | 150 | ||||||||||||
Page Range: | pp. 270-304 | ||||||||||||
DOI: | 10.1016/j.jctb.2020.09.001 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||
Date of first compliant deposit: | 16 September 2020 | ||||||||||||
Date of first compliant Open Access: | 14 September 2021 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year