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

DOI10.1016/J.EJC.2017.07.010zbMATH Open1373.05060arXiv1709.09428OpenAlexW2550344496MaRDI QIDQ1678087FDOQ1678087

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)

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.

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

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

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)

Cites Work

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

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)