Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle.

DOI10.1016/J.JCTB.2016.04.003MaRDI QIDQ290801zbMATHOpenAlexDBLPWikidataFDO

Authors Zdeněk Dvořák, Daniel Král', Robin Thomas

Publication date 3 June 2016

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.2472

zbMATH Keywords

graph coloringplanar graphsprecoloring extension

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

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.

Recommendations

• Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk
• On 3-colorings of plane graphs
• 3-coloring triangle-free planar graphs with a precolored 9-cycle

Cites work

• scientific article; zbMATH DE number 434910 (Why is no real title available?)
• scientific article; zbMATH DE number 3769646 (Why is no real title available?)
• scientific article; zbMATH DE number 3482373 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3450230 (Why is no real title available?)
• 3-list-coloring planar graphs of girth 5
• 4-chromatic projective graphs
• 6-Critical Graphs on the Klein Bottle
• A short list color proof of Grötzsch's theorem
• Color-critical graphs on a fixed surface
• Coloring graphs with fixed genus and girth
• Every Planar Map is Four Colorable
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Five-coloring graphs on the Klein bottle
• Five-coloring graphs on the torus
• Graph theory with applications
• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• Grötzsch's theorem on 3-colorings
• Map-Colour Theorems
• On 3-colorable plane graphs without 5- and 7-cycles
• On a conjecture of B. Grünbaum
• Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
• The chromatic number of a graph of girth 5 on a fixed surface
• The four-colour theorem
• The non-existence of colorings
• Three-coloring Klein bottle graphs of girth five
• Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk
• Three-coloring triangle-free planar graphs in linear time

Cited in

(10)

• Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five
• scientific article; zbMATH DE number 7145382 (Why is no real title available?)
• Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies
• Triangle-free planar graphs with small independence number
• Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk
• Coloring near-quadrangulations of the cylinder and the torus
• Planar graphs without 4-cycles and close triangles are \((2,0,0)\)-colorable
• 3-coloring triangle-free planar graphs with a precolored 9-cycle
• Note on 3-choosability of planar graphs with maximum degree 4
• Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs

This page was built for publication: Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q290801)