Article
A counterexample to a conjecture on facial unique-maximal colorings
Discrete Applied Mathematics
Document Type
Article
Disciplines
Publication Version
Submitted Manuscript
Publication Date
3-11-2018
DOI
10.1016/j.dam.2017.11.037
Abstract
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 [4] 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 [6] later decreased the upper bound from six to five. In this note, we disprove the conjecture by giving an infinite family of counterexamples. s we conclude that facial unique-maximum chromatic number of the sphere is five.
Copyright Owner
Elsevier B.V.
Copyright Date
2017
Language
en
File Format
application/pdf
Citation Information
Bernard Lidicky, Kacy Messerschmidt and Riste Skrekovski. "A counterexample to a conjecture on facial unique-maximal colorings" Discrete Applied Mathematics Vol. 237 (2018) p. 123 - 125 Available at: http://works.bepress.com/bernard-lidicky/56/
This is a manuscript of an article published as Lidický, Bernard, Kacy Messerschmidt, and Riste Škrekovski. "A counterexample to a conjecture on facial unique-maximal colorings." Discrete Applied Mathematics 237 (2018): 123-125. doi: 10.1016/j.dam.2017.11.037. Posted with permission.