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
    0 references
    0 references
    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
    0 references
    0 references
    4-choosable
    0 references
    discharging method
    0 references
    list coloring
    0 references
    planar graphs
    0 references
    0 references
    0 references