Graphs with two crossings are 5-choosable

DOI10.1137/11082703XzbMATH Open1237.05073arXiv1103.1801OpenAlexW2070910247MaRDI QIDQ3225151FDOQ3225151

Authors: Zdeněk Dvořák, Bernard Lidický, Riste Škrekovski 

Publication date: 15 March 2012

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

Abstract: A graph G is k-choosable if G can be properly colored whenever every vertex has a list of at least k available colors. Thomassen's theorem states that every planar graph is 5-choosable. We extend the result by showing that every graph with at most two crossings is 5-choosable.

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

Recommendations

• Planar graphs without intersecting 5-cycles are 4-choosable
• 5-choosability of graphs with crossings far apart
• Planar graphs without chordal 6-cycles are 4-choosable
• Coloring graphs with crossings
• Choosability of \(K_5\)-minor-free graphs

zbMATH Keywords

graph coloringchoosabilitycrossing number

Mathematics Subject Classification ID

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

Cited In (7)

• Thomassen's choosability argument revisited
• 2-connected chordal graphs and line graphs are \((1,5)\)-choosable
• 5-choosability of graphs with crossings far apart
• Graphs of degree 4 are 5-edge-choosable
• IC-planar graphs are 6-choosable
• A note on the list vertex-arboricity of IC-planar graphs
• Graphs with two crossings are 5-DP-colorable

This page was built for publication: Graphs with two crossings are 5-choosable

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