Campus Units

Mathematics

Document Type

Article

Publication Version

Submitted Manuscript

Publication Date

3-11-2018

Journal or Book Title

Discrete Applied Mathematics

Volume

237

First Page

123

Last Page

125

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.

Comments

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.

Language

en

File Format

application/pdf

Published Version

Share

COinS