Exponentially many 5-list-colorings of planar graphs (Q885292): Difference between revisions

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.