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

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

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

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 graph; 3-coloring; critical graph; coloring extension; precolored cycle

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C38: Paths and cycles

05C10: Planar graphs; geometric and topological aspects of graph theory

05C15: Coloring of graphs and hypergraphs

05C12: Distance in graphs