Exponentially many 5-list-colorings of planar graphs (Q885292)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Exponentially many 5-list-colorings of planar graphs
scientific article

    Statements

    Exponentially many 5-list-colorings of planar graphs (English)
    0 references
    8 June 2007
    0 references
    The author proves the following results: Let \(G\) be a plane near-triangulation with outer cycle \(C: v_1v_2\cdots v_k v_1\). For each vertex \(v\) in \(G\), let \(L(v)\) be a list of colors. Assume that the vertices \(v_k\), \(v_1\), \(v_2\) or the vertices \(v_1\),\(v_2\) are precolored. If \(v\) is one of \(v_3,v_4,\dots, v_{k-1}\) (respectively \(v_3,v_4,\dots, v_k\)), then \(L(v)\) consists of at least three colors. Otherwise, \(L(v)\) has at least five colors. Let \(n\) denote the number of non-precolored vertices, and let \(r\) denote the number of vertices with precisely three available colors. Assume that \(G\) has an \(L\)-coloring. Then the number of distinct \(L\)-colorings of \(G\) is at leat \(2^{n/9- r/3}\), unless \(G\) has three precolored vertices and also contains a vertex with precisely four available colors which is joined to the three precolored vertices and has only one available color distinct from the colors of the three precolored vertices. Some problems are posed, too.
    0 references
    planar graph
    0 references
    list colorings
    0 references
    triangulation
    0 references
    0 references

    Identifiers