K₅-free bound for the class of planar graphs

DOI10.1016/J.EJC.2006.06.009MaRDI QIDQ852707zbMATH OpenOpenAlexFDO

Authors Reza Naserasr

Publication date 15 November 2006

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2006.06.009

zbMATH Keywords

graph homomorphismvertex colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

The author defines a \(k\)-diverse colouring of a graph \(G\) to be a proper vertex colouring of \(G\) such that each vertex \(x\) is neighbouring to at least \(\min\{k,d(x)\}\) colours. Given \(k\geq 11\) it is proved via induction that every planar graph admits a \(k\)-diverse colouring using at most \(5k+8\) colours. This is used to produce a \(K_5\)-free bound \(H\) for the class of planar graphs (i.e., each planar graph admits a homomorphism to \(H)\).

Recommendations

• Dynamic coloring of graphs having no \(K_5\) minor
• The edge colorings of \(K_5\)-minor free graphs
• \(k\)-fold \( (2k+2)\)-coloring of planar graphs
• Plane graphs with maximum degree 5 are 11-linear-colorable
• A sufficient condition for a planar graph of maximum degree five to be class 1

Cites work

• Folding
• Homomorphism bounded classes of graphs
• Homomorphisms and edge-colourings of planar graphs
• scientific article; zbMATH DE number 2209736 (Why is no real title available?)
• Universal H-colorable graphs without a given configuration

Cited in

(2)

• Planar graphs are \(9/2\)-colorable
• Bounding the number of embeddings of 5-connected projective-planar graphs

This page was built for publication: \(K_{5}\)-free bound for the class of planar graphs

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