Choosability with separation of planar graphs without prescribed cycles

摘要

In terms of constraining the list assignment, one refinement of k-choosability is considered as choosability with separation. We call a graph (k, d)-choosable if it is colorable from lists of size k where adjacent vertices have at most d common colors in their lists. If two cycles have exactly one common edge, then they are said to be normally adjacent.In this article, it is shown that planar graphs without 5-cycles and normally adjacent 4-cycles are (3,1)-choosable. This extends a result that planar graphs without 5- and 6-cycles are (3,1)-choosable (Choi et al. (2016))