Planar graphs without pairwise adjacent 3-, 4-, 5-, and 6-cycle are 4-choosable (Q2078245)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Planar graphs without pairwise adjacent 3-, 4-, 5-, and 6-cycle are 4-choosable |
scientific article |
Statements
Planar graphs without pairwise adjacent 3-, 4-, 5-, and 6-cycle are 4-choosable (English)
0 references
28 February 2022
0 references
A \(k\)-list assignment of a graph \(G\) assigns a list \(L(v)\) of at least \(k\) colors to each vertex \(v\) of \(G\). A graph \(G\) is \(k\)-choosable if for every \(k\)-list assignment \(L\) of \(G\) there exists a proper coloring \(\varphi\) of the vertices of \(G\) such that \(\varphi(v)\in L(v)\) for each vertex \(v\). Solving a conjecture by P. Erdős, a celebrated result by \textit{C. Thomassen} [J. Comb. Theory, Ser. B 62, No. 1, 180--181 (1994; Zbl 0805.05023)] implies that every planar graph is \(5\)-choosable. Voigt was the first to present a planar graph that is not \(4\)-choosable. A popular and important line of research is verifying sufficient conditions for a planar graph to be \(4\)-choosable, usually by imposing restrictions on cycles. This paper proves that a planar graph without pairwise adjacent \(3\)-, \(4\)-, \(5\)-, \(6\)-cycles are \(4\)-choosable, improving upon some previously known results.
0 references
4-choosable
0 references
discharging method
0 references
list coloring
0 references
planar graphs
0 references