Graphs with two crossings are 5-choosable

DOI10.1137/11082703XMaRDI QIDQ3225151zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

choosabilitycrossing numbergraph coloring

Mathematics Subject Classification ID

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

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.

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₅-minor-free graphs

Cited in

(8)

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

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)