Planar Graphs of Odd-Girth at Least 9 are Homomorphic to the Petersen Graph
From MaRDI portal
Publication:3629463
DOI10.1137/060650507zbMATH Open1167.05313OpenAlexW2045746955WikidataQ122980917 ScholiaQ122980917MaRDI QIDQ3629463FDOQ3629463
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
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)
