Cyclic coloring of plane graphs with maximum face size 16 and 17

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.

Authors	DVOŘÁK Zdeněk HEBDIGE Michael HLÁSEK Filip KRÁĽ Daniel NOEL Jonathan
Year of publication	2021
Type	Article in Periodical
Magazine / Source	European Journal of Combinatorics
MU Faculty or unit	Faculty of Informatics
Citation
Web	http://dx.doi.org/10.1016/j.ejc.2020.103287
Doi	http://dx.doi.org/10.1016/j.ejc.2020.103287
Keywords	graph coloring
Description	Plummer and Toft conjectured in 1987 that the vertices of every 3-connected plane graph with maximum face size Lambda* can be colored using at most Lambda* + 2 colors in such a way that no face is incident with two vertices of the same color. The conjecture has been proven for Lambda* = 3, Lambda* = 4 and Lambda* >= 18. We prove the conjecture for Lambda* = 16 and Lambda* = 17. (c) 2020 Elsevier Ltd. All rights reserved.
Related projects:	MUNI AWARD in Science and Humanitites 1