Choosability of planar graphs

DOI10.1016/0012-365X(95)00216-JMaRDI QIDQ1916256zbMATH OpenFDO

Authors Margit Voigt

Publication date 25 November 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(95)00216-J

zbMATH Keywords

\(k\)-choosablecolouringlist assignment

Mathematics Subject Classification ID

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

Review text

We say the graph \(G= (V, E)\) is \(k\)-choosable if there is at least one \(L\)-list colouring for every possible list assignment \(L\) with \(|L(v)|= k\) for all \(v\in V\). \(G\) is called free \(k\)-choosable if such an \(L\)-list colouring exists for every list assignment \(L\), every vertex \(v\) and every colour \(f\in L(v)\). It is shown that the following conjectures are equivalent: every planar graph is 5-choosable (free 5-choosable).

Recommendations

• Path choosability of planar graphs
• The complexity of planar graph choosability
• The entire choosability of plane graphs
• Minimum choosability of planar graphs
• Choosability in signed planar graphs
• On the total choosability of planar graphs and of sparse graphs
• On structure of some plane graphs with application to choosability
• A note on the minimum number of choosability of planar graphs
• On the choosability of some graphs
• Coupled choosability of plane graphs

Cites work

• Colorings and orientations of graphs
• scientific article; zbMATH DE number 3920498 (Why is no real title available?)
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• List T-colorings of graphs
• List colourings of planar graphs
• Multicriterial graph problems with MAXMIN criterion

Cited in

(16)

• Every planar graph is 5-choosable
• Choosability of K₅-minor-free graphs
• Path choosability of planar graphs
• Choosability, edge choosability and total choosability of outerplane graphs
• The edge-face choosability of plane graphs
• Incidence choosability of graphs
• An algebraic criterion for the choosability of graphs
• List colourings of planar graphs. (Reprint)
• Every triangle-free induced subgraph of the triangular lattice is \((5m,2m)\)-choosable
• 2-distance choosability of planar graphs with a restriction for maximum degree
• (4,1)^*-choosability of planar graphs
• Circular choosability of planar graphs with large girth.
• Free choosability of outerplanar graphs
• Multiple list colouring of planar graphs
• List colourings of planar graphs
• Another proof of the 5-choosability of \(K_5\)-minor-free graphs

This page was built for publication: Choosability of planar graphs

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