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:

You are running an old browser version. We recommend updating your browser to its latest version.