Campus Units

Mathematics, Computer Science

Document Type

Article

Publication Version

Published Version

Publication Date

3-2016

Journal or Book Title

Journal of Graph Theory

Volume

81

Issue

3

First Page

283

Last Page

306

DOI

10.1002/jgt.21875

Abstract

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.

Comments

This article is published as Choi, Ilkyoo, Bernard Lidický, and Derrick Stolee. "On choosability with separation of planar graphs with forbidden cycles." Journal of Graph Theory 81, no. 3 (2016): 283-306. doi: 10.1002/jgt.21875. Posted with permission.

Copyright Owner

Wiley Periodicals, Inc.

Language

en

File Format

application/pdf

Share

COinS