(4,2)-choosability of planar graphs with forbidden structures

DOI10.1007/S00373-017-1812-5MaRDI QIDQ2409516zbMATH OpenOpenAlexFDO

Authors Zhanar Berikkyzy, Christopher Cox, Michael Dairyko, Kirsten Hogenson, M. Kumbhat, Bernard Lidický, Kacy Messerschmidt, Kevin Moss, Kathleen Nowak, Kevin F. Palmowski, Derrick Stolee

Publication date 11 October 2017

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

choosability with separationdischarginggraph coloringplanar graph

Mathematics Subject Classification ID

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

Abstract: All planar graphs are 4-colorable and 5-choosable, while some planar graphs are not 4-choosable. Determining which properties guarantee that a planar graph can be colored using lists of size four has received significant attention. In terms of constraining the structure of the graph, for any $ellin3,4,5,6,7$, a planar graph is 4-choosable if it is $ell$-cycle-free. In terms of constraining the list assignment, one refinement of $k$-choosability is choosability with separation. A graph is $(k,s)$-choosable if the graph is colorable from lists of size $k$ where adjacent vertices have at most $s$ common colors in their lists. Every planar graph is $(4,1)$-choosable, but there exist planar graphs that are not $(4,3)$-choosable. It is an open question whether planar graphs are always $(4,2)$-choosable. A chorded $ell$-cycle is an $ell$-cycle with one additional edge. We demonstrate for each $ellin5,6,7$ that a planar graph is $(4,2)$-choosable if it does not contain chorded $ell$-cycles.

Recommendations

• (4,1)^*-choosability of planar graphs
• \((4m,m)\)-choosability of plane graphs
• On \((4,2)\)-choosable graphs
• The 4-choosability of planar graphs and cycle adjacency
• Acyclic 4-choosability of planar graphs
• 4-choosability of planar graphs with 4-cycles far apart via the Combinatorial Nullstellensatz
• The 4-choosability of plane graphs without 4-cycles
• Total choosability of planar graphs with maximum degree 4
• A characterization of \((4,2)\)-choosable graphs
• On choosability with separation of planar graphs with forbidden cycles

Cites work

• A note on choosability with separation for planar graphs.
• An introduction to the discharging method via graph coloring
• Brooks-type theorems for choosability with separation
• Choosability and edge choosability of planar graphs without five cycles
• Colorings and orientations of graphs
• Colorings of plane graphs: a survey
• Every planar graph is 5-choosable
• List colourings of planar graphs
• On choosability with separation of planar graphs with forbidden cycles
• On choosability with separation of planar graphs with lists of different sizes
• Planar Graphs without 7-Cycles Are 4-Choosable
• Planar graphs without cycles of specific lengths
• Planar graphs without triangular 4-cycles are 3-choosable
• The 4-choosability of plane graphs without 4-cycles

Cited in

(7)

• Choosability with union separation
• On the \((3, 1)\)-choosability of planar graphs without adjacent cycles of length \(5, 6, 7\)
• (4,1)^*-choosability of planar graphs
• List 4-colouring of planar graphs
• On list coloring with separation of the complete graph and set system intersections
• Choosability with separation of cycles and outerplanar graphs
• On choosability with separation of K₅-minor-free graphs

This page was built for publication: \((4,2)\)-choosability of planar graphs with forbidden structures

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