WorksMathematics
Weak Degeneracy with Availability for Planar Graphs
Abstract
Every planar graph admits exponentially many proper colorings for any assignment of lists of five allowed colors to its vertices. In this paper, we show that very little beyond degeneracy is needed to prove that this statement holds. In particular, given a planar graph G (but not the list assignment), our argument provides an algorithm consisting entirely of instructions of the following form: Color the vertex v using any color c from its list, and remove c from the lists of neighbors of v.'' and For the edge uv, choose any k colors from the list of u, then color v by any color c from its list that does not appear among these k colors, and remove c from the lists of neighbors of v.'' For every assignment of lists of size five to vertices of G, following this algorithm in all possible ways guarantees that at least different proper colorings of G are produced (and at least one color choice is guaranteed to be available in each step). We also show that this result has the following consequence: for every planar graph G, there exists a set of size at least 0.06|V(G)| such that G can be properly colored from any assignment of lists of size four to vertices in R and lists of size five to the rest of vertices of G. Moreover, these statements remain true even in stronger settings, such as for correspondence coloring.