List 4-colouring of planar graphs

DOI10.1016/J.JCTB.2023.04.001MaRDI QIDQ6170786zbMATH OpenFDO

Authors Xuding Zhu

Publication date 10 August 2023

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

planar graphlist colouringlists with separation

Mathematics Subject Classification ID

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

Abstract: This paper proves the following result: If $G$ is a planar graph and $L$ is a $4$-list assignment of $G$ such that $|L(x)capL(y)|le2$ for every edge $xy$, then $G$ is $L$-colourable. This answers a question asked by Kratochv'{i}l, Tuza and Voigt in [Journal of Graph Theory, 27(1):43--49, 1998].

Recommendations

• List coloring triangle-free planar graphs
• A local condition for planar graphs to be 4-choosable
• List colourings of planar graphs
• Multiple list colouring of planar graphs
• The choosability of some 4-reduced plane graphs

Cites work

• scientific article; zbMATH DE number 890665 (Why is no real title available?)
• A note on choosability with separation for planar graphs.
• A note on not-4-list colorable planar graphs
• A refinement of choosability of graphs
• Brooks-type theorems for choosability with separation
• Choosability with separation of complete multipartite graphs and hypergraphs
• Choosability with union separation
• Choosability with union separation of triangle-free planar graphs
• Coloring face-hypergraphs of graphs on surfaces
• Every planar graph is 5-choosable
• List colourings of planar graphs
• On \(t\)-common list-colorings
• On choosability with separation of planar graphs with forbidden cycles
• On choosability with separation of planar graphs with lists of different sizes
• On the \((3, 1)\)-choosability of planar graphs without adjacent cycles of length \(5, 6, 7\)
• Separation choosability and dense bipartite induced subgraphs
• Single‐conflict colouring
• The four-colour theorem
• \((4,2)\)-choosability of planar graphs with forbidden structures

Cited in

(7)

• Flexibility of planar graphs -- sharpening the tools to get lists of size four
• List coloring triangle-free planar graphs
• scientific article; zbMATH DE number 5936522 (Why is no real title available?)
• A note on not-4-list colorable planar graphs
• A note on planar 5-list colouring: Non-extendability at distance 4
• List Colouring Squares of Planar Graphs
• List dynamic 4-coloring of planar graphs

This page was built for publication: List 4-colouring of planar graphs

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