3-coloring triangle-free planar graphs with a precolored 9-cycle

DOI10.1016/J.EJC.2017.07.010MaRDI QIDQ1678087zbMATH OpenOpenAlexFDO

Authors Ilkyoo Choi, Jan Ekstein, Přemysl Holub, Bernard Lidický

Publication date 14 November 2017

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

triangle-free planar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Abstract: Given a triangle-free planar graph G and a 9-cycle C in G, we characterize situations where a 3-coloring of C does not extend to a proper 3-coloring of G. This extends previous results when C is a cycle of length at most 8.

Recommendations

• Fine Structure of 4-Critical Triangle-Free Graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains
• Fine structure of 4-critical triangle-free graphs. II: Planar triangle-free graphs with two precolored 4-cycles
• Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable

Cites work

• 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 1882353 (Why is no real title available?)
• scientific article; zbMATH DE number 2097483 (Why is no real title available?)
• 4-critical graphs on surfaces without contractible \((\leq 4)\)-cycles
• A Contribution to the Theory of Chromatic Polynomials
• A new proof of Grünbaum's 3 color theorem
• Coloring graphs with fixed genus and girth
• Colorings of plane graphs: a survey
• Continuation of a 3-coloring from a 7-face onto a plane graph without \(C_3\)
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Grötzsch's theorem on 3-colorings
• Planar 4-critical graphs with four triangles
• Short proofs of coloring theorems on planar graphs
• The chromatic number of a graph of girth 5 on a fixed surface
• The four-colour theorem
• Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle.
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete

Cited in

(3)

• Further extensions of the Grötzsch theorem
• Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle.
• Fine structure of 4-critical triangle-free graphs. II: Planar triangle-free graphs with two precolored 4-cycles

This page was built for publication: 3-coloring triangle-free planar graphs with a precolored 9-cycle

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