Coloring of plane graphs with unique maximal colors on faces

DOI10.1002/JGT.22002zbMATH Open1352.05073arXiv1409.2250OpenAlexW2228680997MaRDI QIDQ2833253FDOQ2833253

Authors: Alex Wendland 

Publication date: 17 November 2016

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

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.

Full work available at URL: https://arxiv.org/abs/1409.2250

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

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)

Cites Work

• Every planar graph is 5-choosable
• List colourings of planar graphs
• Title not available (Why is that?)

Cited In (14)

• A note on face coloring entire weightings of plane graphs
• Facial unique-maximum colorings of plane graphs with restriction on big vertices
• 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
• A new proof of the 6 color theorem

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)