The Library
Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle
Tools
Dvorak, Zdenek, Králʼ, Daniel and Thomas, Robin (2016) Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle. Journal of Combinatorial Theory, Series B, 120 . pp. 1-17. doi:10.1016/j.jctb.2016.04.003 ISSN 0095-8956.
|
PDF
WRAP_1173667-ma-020416-disk %28002%29.pdf - Accepted Version - Requires a PDF viewer. Download (519Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.jctb.2016.04.003
Abstract
Let G be a plane graph with exactly one triangle T and all other cycles of length at least 5, and let C be a facial cycle of G of length at most six. We prove that a 3-coloring of C does not extend to a 3-coloring of G if and only if C has length exactly six and there is a color x such that either G has an edge joining two vertices of C colored x, or T is disjoint from C and every vertex of T is adjacent to a vertex of C colored x. This is a lemma to be used 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 coloring , Triangle, Sphere | ||||||||||
Journal or Publication Title: | Journal of Combinatorial Theory, Series B | ||||||||||
Publisher: | Academic Press | ||||||||||
ISSN: | 0095-8956 | ||||||||||
Official Date: | September 2016 | ||||||||||
Dates: |
|
||||||||||
Volume: | 120 | ||||||||||
Page Range: | pp. 1-17 | ||||||||||
DOI: | 10.1016/j.jctb.2016.04.003 | ||||||||||
Status: | Peer Reviewed | ||||||||||
Publication Status: | Published | ||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||
Date of first compliant deposit: | 4 April 2016 | ||||||||||
Date of first compliant Open Access: | 18 April 2017 | ||||||||||
Funder: | National Science Foundation (U.S.) (NSF), Czech Science Foundation (CSF) | ||||||||||
Grant number: | MS-0701077 (NSF), project P202/12/G061 (CSF) | ||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year