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

DOI10.1016/J.DISC.2015.01.008zbMATH Open1315.05038arXiv1306.5283OpenAlexW1991475475MaRDI QIDQ2346342FDOQ2346342

Authors: Bernard Lidický, H. A. Kierstead 

Publication date: 1 June 2015

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: A (k,d)-list assignment L of a graph G is a mapping 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. 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.

Full work available at URL: https://arxiv.org/abs/1306.5283

Recommendations

• On choosability with separation of planar graphs without adjacent short cycles
• On choosability with separation of planar graphs with forbidden cycles
• A sufficient condition for planar graphs to be (3,1)-choosable
• A note on adaptable choosability and choosability with separation of planar graphs
• Choosability with separation of planar graphs without prescribed cycles

zbMATH Keywords

graph coloringlist coloringplanar graphschoosability with separation

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Every planar graph is 5-choosable
• Brooks-type theorems for choosability with separation
• Choosability with separation of complete multipartite graphs and hypergraphs
• List colourings of planar graphs
• A not 3-choosable planar graph without 3-cycles
• A note on choosability with separation for planar graphs.

Cited In (10)

• List 4-colouring of planar graphs
• Flexibility of planar graphs -- sharpening the tools to get lists of size four
• Separation choosability and dense bipartite induced subgraphs
• On choosability with separation of planar graphs without adjacent short cycles
• A note on adaptable choosability and choosability with separation of planar graphs
• A sufficient condition for planar graphs to be (3,1)-choosable
• Choosability with union separation
• A note on choosability with separation for planar graphs.
• On choosability with separation of planar graphs with forbidden cycles
• \((4,2)\)-choosability of planar graphs with forbidden structures

This page was built for publication: On choosability with separation of planar graphs with lists of different sizes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2346342)