Coloring of plane graphs with unique maximal colors on faces

DOI10.1002/JGT.22002MaRDI QIDQ2833253zbMATH OpenOpenAlexFDO

Authors Alex Wendland

Publication date 17 November 2016

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.2250, http://wrap.warwick.ac.uk/73823/7/WRAP_1104375-ma-271015-colouring.pdf

zbMATH Keywords

plane graphscapital \(k\)-choosabilitycapital graph coloring

Mathematics Subject Classification ID

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

Abstract: The Four Colour Theorem asserts that the vertices of every plane graph can be properly coloured with four colors. Fabrici and G"oring conjectured the following stronger statement to also hold: the vertices of every plane graph can be properly coloured with the numbers 1,...,4 in such a way that every face contains a unique vertex coloured with the maximal color appearing on that face. They proved that every plane graph has such a colouring with the numbers 1,...,6. We prove that every plane graph has such a colouring with the numbers 1,...,5 and we also prove the list variant of the statement for lists of sizes seven.

Recommendations

• On facial unique-maximum (edge-)coloring
• Facial unique-maximum colorings of plane graphs with restriction on big vertices
• Unique-maximum coloring of plane graphs
• A counterexample to a conjecture on facial unique-maximal colorings
• Colouring vertices of plane graphs under restrictions given by faces

Cites work

• scientific article; zbMATH DE number 1021588 (Why is no real title available?)
• Every planar graph is 5-choosable
• List colourings of planar graphs

Cited in

(14)

• A new proof of the 6 color theorem
• Facial unique-maximum colorings of plane graphs with restriction on big vertices
• A note on face coloring entire weightings of plane graphs
• A survey on the cyclic coloring and its relaxations
• Colorability of planar graphs with isolated nontriangular faces
• Coloring count cones of planar graphs
• Facially-constrained colorings of plane graphs: a survey
• Facial unique-maximum edge and total coloring of plane graphs
• Maximum face-constrained coloring of plane graphs
• Unique-maximum coloring of plane graphs
• Colouring vertices of plane graphs under restrictions given by faces
• A counterexample to a conjecture on facial unique-maximal colorings
• On facial unique-maximum (edge-)coloring
• Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods

This page was built for publication: Coloring of plane graphs with unique maximal colors on faces

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