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

Date
2015-10-06
Authors
Kierstead, H.
Lidicky, Bernard
Lidicky, Bernard
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Department
Mathematics
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.

Comments

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: 10.1016/j.disc.2015.01.008. Posted with permission.

Description
Keywords
Citation
DOI
Collections