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

dc.contributor.author Kierstead, H.
dc.contributor.author Lidicky, Bernard
dc.contributor.author Lidicky, Bernard
dc.contributor.department Mathematics
dc.date 2018-02-18T23:29:50.000
dc.date.accessioned 2020-06-30T05:59:44Z
dc.date.available 2020-06-30T05:59:44Z
dc.date.copyright Thu Jan 01 00:00:00 UTC 2015
dc.date.issued 2015-10-06
dc.description.abstract <p><p id="x-x-x-sp000015">A (k,d)(k,d)<em>-list assignment </em>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. <p id="x-x-x-sp000020">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. <p id="x-x-x-sp000025">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.</p>
dc.description.comments <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>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/math_pubs/126/
dc.identifier.articleid 1131
dc.identifier.contextkey 10852585
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath math_pubs/126
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/54509
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/math_pubs/126/2015_Lidicky_ChoosabilitySeparation.pdf|||Fri Jan 14 19:25:36 UTC 2022
dc.source.uri 10.1016/j.disc.2015.01.008
dc.subject.disciplines Discrete Mathematics and Combinatorics
dc.subject.keywords Graph coloring
dc.subject.keywords Planar graphs
dc.subject.keywords Choosability with separation
dc.subject.keywords List coloring
dc.title On choosability with separation of planar graphs with lists of different sizes
dc.type article
dc.type.genre article
dspace.entity.type Publication
relation.isAuthorOfPublication a1d8f5ab-9124-4104-981c-8ba1e426e3ff
relation.isOrgUnitOfPublication 82295b2b-0f85-4929-9659-075c93e82c48
File
Original bundle
Now showing 1 - 1 of 1
Name:
2015_Lidicky_ChoosabilitySeparation.pdf
Size:
275.69 KB
Format:
Adobe Portable Document Format
Description:
Collections