A counterexample to a conjecture on facial unique-maximal colorings

Date
2018-03-11
Authors
Lidicky, Bernard
Messerschmidt, Kacy
Skrekovski, Riste
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
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.

Description

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.

Keywords
facial unique-maximum coloring, plane graph
Citation
DOI
Collections