3-Coloring Triangle-Free Planar Graphs with a Precolored 9-Cycle

DOI10.1007/978-3-319-19315-1_9zbMath1401.05106arXiv1305.2467OpenAlexW2963945947MaRDI QIDQ2946045

Přemysl Holub, Bernard Lidický, Ilkyoo Choi, Jan Ekstein, Zdeněk Dvořák

Publication date: 15 September 2015

Published in: Lecture Notes in Computer Science, Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

planar graph3-coloringcritical graphcoloring extensionprecolored cycle

Mathematics Subject Classification ID

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

Related Items (max. 100)

Further extensions of the Grötzsch theorem ⋮ Triangle-free planar graphs with small independence number ⋮ Fine Structure of 4-Critical Triangle-Free Graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains ⋮ Characterization of 4-critical triangle-free toroidal graphs ⋮ 3-coloring triangle-free planar graphs with a precolored 9-cycle ⋮ 3-Coloring Triangle-Free Planar Graphs with a Precolored 9-Cycle ⋮ Fractional coloring of triangle-free planar graphs ⋮ Coloring near-quadrangulations of the cylinder and the torus ⋮ Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Five-list-coloring graphs on surfaces. II: A linear bound for critical graphs in a disk.
• Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle.
• Planar 4-critical graphs with four triangles
• 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
• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• A new proof of Grünbaum's 3 color theorem
• The four-colour theorem
• Color-critical graphs on a fixed surface
• The chromatic number of a graph of girth 5 on a fixed surface
• Colorings of plane graphs: a survey
• Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs
• Short proofs of coloring theorems on planar graphs
• Continuation of a 3-coloring from a 7-face onto a plane graph without \(C_3\)
• Grötzsch's theorem on 3-colorings
• 3-Coloring Triangle-Free Planar Graphs with a Precolored 9-Cycle
• Coloring graphs with fixed genus and girth
• The color space of a graph
• 4-Critical Graphs on Surfaces Without Contractible $(\le\!4)$-Cycles
• A Contribution to the Theory of Chromatic Polynomials

This page was built for publication: 3-Coloring Triangle-Free Planar Graphs with a Precolored 9-Cycle