On choosability with separation of planar graphs with forbidden cycles

DOI10.1002/JGT.21875zbMATH Open1333.05086arXiv1303.2753OpenAlexW1941702003MaRDI QIDQ2800544FDOQ2800544

Bernard Lidický, Ilkyoo Choi, Derrick Stolee

Publication date: 15 April 2016

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: 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.

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

zbMATH Keywords

\((k,d)\)-list assignment

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)

Cites Work

• Colorings of plane graphs: a survey
• Every planar graph is 5-choosable
• 3-list-coloring planar graphs of girth 5
• 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.
• A smaller planar graph without 4-, 5-cycles and intersecting triangles that is not 3-choosable

Cited In (11)

• List 4-colouring of planar graphs
• Title not available (Why is that?)
• On choosability with separation of planar graphs without adjacent short cycles
• IC-Planar Graphs Are 6-Choosable
• Choosability with union separation of planar graphs without cycles of length 4
• Choosability with separation of planar graphs without prescribed cycles
• On the \((3, 1)\)-choosability of planar graphs without adjacent cycles of length \(5, 6, 7\)
• A sufficient condition for planar graphs to be (3,1)-choosable
• Choosability with union separation
• A note on choosability with separation for planar graphs.
• \((4,2)\)-choosability of planar graphs with forbidden structures

This page was built for publication: On choosability with separation of planar graphs with forbidden cycles

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