Choosability with separation of planar graphs without prescribed cycles

Min Chen*, Yingying Fan, André Raspaud, Wai Chee Shiu, Weifan Wang

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

2 Citations (Scopus)


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))

Original languageEnglish
Article number124756
JournalApplied Mathematics and Computation
Publication statusPublished - 15 Feb 2020

Scopus Subject Areas

  • Computational Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Adjacent cycles
  • Choosability with separation
  • List coloring
  • Planar graphs


Dive into the research topics of 'Choosability with separation of planar graphs without prescribed cycles'. Together they form a unique fingerprint.

Cite this