The Library
Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies
Tools
Dvořák, Zdeněk, Králʼ, Daniel and Thomas, Robin (2021) Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies. Journal of Combinatorial Theory Series B, 150 . pp. 244-269. doi:10.1016/j.jctb.2020.04.006 ISSN 0095-8956.
|
PDF
WRAP-Three-coloring-triangle-free-surfaces-Kral-2020.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (478Kb) | Preview |
Official URL: https://doi.org/10.1016/j.jctb.2020.04.006
Abstract
We settle a problem of Havel by showing that there exists an absolute constant d such that if G is a planar graph in which every two distinct triangles are at distance at least d, then G is 3-colorable. In fact, we prove a more general theorem. Let G be a planar graph, and let H be a set of connected subgraphs of G, each of bounded size, such that every two distinct members of H are at least a specified distance apart and all triangles of G are contained in \bigcup{H}. We give a sufficient condition for the existence of a 3-coloring phi of G such that for every B\in H, the restriction of phi to B is constrained in a specified way.
Item Type: | Journal Article | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | |||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | |||||||||||||||
Library of Congress Subject Headings (LCSH): | Combinatorial analysis, Algorithms, Graph theory -- Data processing | |||||||||||||||
Journal or Publication Title: | Journal of Combinatorial Theory Series B | |||||||||||||||
Publisher: | Elsevier | |||||||||||||||
ISSN: | 0095-8956 | |||||||||||||||
Official Date: | September 2021 | |||||||||||||||
Dates: |
|
|||||||||||||||
Volume: | 150 | |||||||||||||||
Page Range: | pp. 244-269 | |||||||||||||||
DOI: | 10.1016/j.jctb.2020.04.006 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||
Date of first compliant deposit: | 1 May 2020 | |||||||||||||||
Date of first compliant Open Access: | 5 May 2021 | |||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||
Related URLs: | ||||||||||||||||
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