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