On choosability with separation of planar graphs with lists of different sizes

Date
2015-10-06
Authors
Kierstead, H.
Lidicky, Bernard
Lidicky, Bernard
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Abstract

A (k,d)(k,d)-list assignment LL of a graph GG is a mapping that assigns to each vertex vv a list L(v)L(v) of at least kk colors and for any adjacent pair xyxy, the lists L(x)L(x) and L(y)L(y) share at most dd colors. A graph GG is (k,d)(k,d)-choosable if there exists an LL-coloring of GG for every (k,d)(k,d)-list assignment LL. This concept is also known as choosability with separation.

It is known that planar graphs are (4, 1)-choosable but it is not known if planar graphs are (3, 1)-choosable. We strengthen the result that planar graphs are (4, 1)-choosable by allowing an independent set of vertices to have lists of size 3 instead of 4.

Our strengthening is motivated by the observation that in (4, 1)-list assignment, vertices of an edge have together at least 7 colors, while in (3, 1)-list assignment, they have only at least 5. Our setting gives at least 6 colors.

Description
<p>This article is published as Kierstead, Hal A., and Bernard Lidický. "On choosability with separation of planar graphs with lists of different sizes." Discrete Mathematics 338, no. 10 (2015): 1779-1783. doi: <a href="http://dx.doi.org/10.1016/j.disc.2015.01.008" target="_blank">10.1016/j.disc.2015.01.008</a>. Posted with permission.</p>
Keywords
Graph coloring, Planar graphs, Choosability with separation, List coloring
Citation
Collections