Skip to main content
A counterexample to a conjecture on facial unique-maximal colorings
Discrete Applied Mathematics
  • Bernard Lidicky, Iowa State University
  • Kacy Messerschmidt, Iowa State University
  • Riste Skrekovski, Novo mesto & University of Ljubljana
Document Type
Publication Version
Submitted Manuscript
Publication Date

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.


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.

Copyright Owner
Elsevier B.V.
File Format
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: