A counterexample to a conjecture on facial unique-maximal colorings

A facial unique-maximum coloring of a plane graph is a proper vertex coloring by natural numbers where on each face α the maximal color appears exactly once on the vertices of α. Fabrici and Göring (2016) proved that six colors are enough for any plane graph and conjectured that four colors suffice....

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2018-03, Vol.237, p.123-125
Main Authors: Lidický, Bernard, Messerschmidt, Kacy, Škrekovski, Riste
Format: Article
Language:English
Subjects:
Color
Facial unique-maximum coloring
Four color problem
Graph coloring
Graphs
Mathematics
Number theory
Numbers
Plane graph
Theorems
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A facial unique-maximum coloring of a plane graph is a proper vertex coloring by natural numbers where on each face α the maximal color appears exactly once on the vertices of α. Fabrici and Göring (2016) proved that six colors are enough for any plane graph and conjectured that four colors suffice. This conjecture is a strengthening of the Four Color Theorem. Wendland (2016) later decreased the upper bound from six to five. In this note, we disprove the conjecture by giving an infinite family of counterexamples. Thus we conclude that the facial unique-maximum chromatic number of the sphere is five.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2017.11.037