betaFeedback

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 2∣V(G)∣/72^{|V(G)|/7} 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 R⊆V(G)R\subseteq V(G) 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.

Paper details

vlnc:W_pb5tj96b
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…