Planar Graphs of Odd-Girth at Least 9 are Homomorphic to the Petersen Graph

DOI10.1137/060650507MaRDI QIDQ3629463zbMATH OpenOpenAlexWikidataFDO

Authors Zdeněk Dvořák, Riste Škrekovski, T. Valla

Publication date 27 May 2009

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/de2eee0c1f612499f1080f3ad5b1bf8848d6d6eb

zbMATH Keywords

girthhomomorphismplanar graphscoloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• Planar graphs are \(9/2\)-colorable
• Every planar graph with girth at least 5 is (1,9)-colorable
• Planar graphs with \(\Delta \geq 9\) are entirely \((\Delta+2)\)-colorable
• Extremal \(P_8\)-free/\(P_9\)-free planar graphs
• Planar graphs with \(\Delta =9\) are neighbor-distinguishing totally 12-colorable
• Decomposing a planar graph with girth 9 into a forest and a matching
• Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable
• Planar graphs without cycles of length 4, 5, 8, or 9 are 3-choosable
• Odd induced subgraphs in planar graphs with large girth
• Planar graphs without cycles of length 4 or 9 are $\boldsymbol{(2,~0,~0)}$-colorable

Cited in

(8)

• Homomorphisms from sparse graphs to the Petersen graph
• Mapping planar graphs into projective cubes
• On the odd girth and the circular chromatic number of generalized Petersen graphs
• Fractional coloring planar graphs under Steinberg-type conditions
• Mapping planar graphs into the Coxeter graph
• Large independent sets in triangle-free planar graphs
• Approximability Distance in the Space of H-Colourability Problems
• Planar graphs without cycles of length 4 or 5 are \((11 : 3)\)-colorable

This page was built for publication: Planar Graphs of Odd-Girth at Least 9 are Homomorphic to the Petersen Graph

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