On choosability with separation of planar graphs with forbidden cycles

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

Authors Ilkyoo Choi, Bernard Lidický, Derrick Stolee

Publication date 15 April 2016

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

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)

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.

Recommendations

• On choosability with separation of planar graphs without adjacent short cycles
• 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\)
• On choosability with separation of planar graphs with lists of different sizes
• A sufficient condition for planar graphs to be (3,1)-choosable

Cites work

• 3-list-coloring planar graphs of girth 5
• 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
• Brooks-type theorems for choosability with separation
• Choosability with separation of complete multipartite graphs and hypergraphs
• Colorings of plane graphs: a survey
• Every planar graph is 5-choosable
• List colourings of planar graphs

Cited in

(15)

• On the \((3, 1)\)-choosability of planar graphs without adjacent cycles of length \(5, 6, 7\)
• List 4-colouring of planar graphs
• scientific article; zbMATH DE number 4135967 (Why is no real title available?)
• Choosability with union separation of triangle-free planar graphs
• \((4,2)\)-choosability of planar graphs with forbidden structures
• On \((3, r)\)-choosability of some planar graphs
• Choosability with union separation
• Choosability with union separation of planar graphs without cycles of length 4
• A sufficient condition for planar graphs to be (3,1)-choosable
• Separation choosability and dense bipartite induced subgraphs
• On choosability with separation of planar graphs with lists of different sizes
• On choosability with separation of planar graphs without adjacent short cycles
• A note on choosability with separation for planar graphs.
• IC-planar graphs are 6-choosable
• Choosability with separation of planar graphs without prescribed cycles

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)