The Library

Three-coloring triangle-free graphs on surfaces II. 4-critical graphs in a disk

Tools

Dvořák, Zdeněk, Králʼ, Daniel and Thomas, Robin (2018) Three-coloring triangle-free graphs on surfaces II. 4-critical graphs in a disk. Journal of Combinatorial Theory Series B . doi:10.1016/j.jctb.2018.03.001 (In Press)

Preview

PDF
WRAP-Three-colouring-triangle-free-graphs-Kral-2018.pdf - Accepted Version - Requires a PDF viewer.
Download (754Kb) | Preview

Official URL: http://dx.doi.org/10.1016/j.jctb.2018.03.001

Request Changes to record.

Abstract

Let G be a plane graph of girth at least five. We show that if there exists a 3-coloring of a cycle C of G that does not extend to a 3-coloring of G, then G has a subgraph H on O(|C|) vertices that also has no 3-coloring extending. This is asymptotically best possible and improves a previous bound of Thomassen. In the next paper of the series we will use this result and the attendant theory to prove a generalization to graphs on surfaces with several precolored cycles.

Item Type:

Journal Article

Subjects:

Q Science > QA Mathematics

Divisions:

Faculty of Science > Mathematics

Library of Congress Subject Headings (LCSH):

Graph coloring

Journal or Publication Title:

Journal of Combinatorial Theory Series B

Publisher:

Elsevier

ISSN:

0095-8956

Official Date:

27 March 2018

Dates:

Date	Event
27 March 2018	Available
3 March 2018	Accepted

Date of first compliant deposit:

5 March 2018

DOI:

10.1016/j.jctb.2018.03.001

Status:

Peer Reviewed

Publication Status:

In Press

Access rights to Published version:

Restricted or Subscription Access

RIOXX Funder/Project Grant:

Project/Grant ID	RIOXX Funder Name	Funder ID
GACR 201/09/0197	Grantová Agentura České Republiky	http://dx.doi.org/10.13039/501100001824
P202/12/G061	Grantová Agentura České Republiky	http://dx.doi.org/10.13039/501100001824
DMS-0739366	National Science Foundation	http://dx.doi.org/10.13039/100000001
DMS-1202640	National Science Foundation	http://dx.doi.org/10.13039/100000001