Mathematics, Computer Science
Journal or Book Title
Journal of Graph Theory
We study choosability with separation which is a constrained version of list coloring of graphs. A -list assignment L of a graph G is a function that assigns to each vertex v a list of at least k colors and for any adjacent pair , the lists and share at most d colors. A graph G is -choosable if there exists an L-coloring of G for every -list assignment L. This concept is also known as choosability with separation. We prove that planar graphs without 4-cycles are (3, 1)-choosable and that planar graphs without 5- and 6-cycles are (3, 1)-choosable. In addition, we give an alternative and slightly stronger proof that triangle-free planar graphs are (3, 1)-choosable.
Wiley Periodicals, Inc.
Choi, Ilkyoo; Lidicky, Bernard; and Stolee, Derrick, "On Choosability with Separation of Planar Graphs with Forbidden Cycles" (2016). Mathematics Publications. 118.