Coloring of Plane Graphs with Unique Maximal Colors on Faces |
| |
| Authors: | Alex Wendland |
| |
| Affiliation: | WARWICK INSTITUTE OF MATHEMATICS, UNIVERSITY OF WARWICK, COVENTRY, UNITED KINGDOMThis research was done during the author's visit to Charles University in Prague and University of West Bohemia in Pilsen, which was supported by Undergraduate Research Support Scheme of the University of Warwick and the Graph Colouring and structure Grant of the Czech Science Foundation. Contract grant number: GA14‐19503S. |
| |
| Abstract: | The Four Color Theorem asserts that the vertices of every plane graph can be properly colored with four colors. Fabrici and Göring conjectured the following stronger statement to also hold: the vertices of every plane graph can be properly colored with the numbers 1, …, 4 in such a way that every face contains a unique vertex colored with the maximal color appearing on that face. They proved that every plane graph has such a coloring with the numbers 1, …, 6. We prove that every plane graph has such a coloring with the numbers 1, …, 5 and we also prove the list variant of the statement for lists of sizes seven. |
| |
| Keywords: | plane graphs vertex coloring coloring with face constraints |
|
|
