On Choosability with Separation of Planar Graphs with Forbidden Cycles

We study choosability with separation which is a constrained version of list coloring of graphs. A (k,d)-list assignment L on a graph G is a function that assigns to each vertex v a list L(v) of at least k colors and for any adjacent pair xy, the lists L(x) and L(y) share at most d colors. A graph G...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2013-03
Main Authors: Choi, Ilkyoo, Lidický, Bernard, Stolee, Derrick
Format: Article
Language:English
Subjects:
Coloring
Graphs
Separation
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study choosability with separation which is a constrained version of list coloring of graphs. A (k,d)-list assignment L on a graph G is a function that assigns to each vertex v a list L(v) of at least k colors and for any adjacent pair xy, the lists L(x) and L(y) share at most d colors. A graph G is (k,d)-choosable if there exists an L-coloring of G for every (k,d)-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-cycles 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.
ISSN:2331-8422
DOI:10.48550/arxiv.1303.2753