2022/11/16 by Kaul, Hemanshu, Mathew, Rogers, Mudrock, Jeffrey A. +1 · 2 citations
#05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2211.09048
Flexible list coloring was introduced by Dvořák, Norin, and Postle in 2019. Suppose 0 ≤ ε≤ 1, G is a graph, L is a list assignment for G, and r is a function with non-empty domain D⊆ V(G) such that r(v) ∈ L(v) for each v ∈ D (r is called a request of L). The triple (G,L,r) is ε-satisfiable if there exists a proper L-coloring f of G such that f(v) = r(v) for at least ε|D| vertices in D. We say G is (k, ε)-flexible if (G,L',r') is ε-satisfiable whenever L' is a k-assignment for G and r' is a request of L'. It was shown by Dvořák et al. that if d+1 is prime, G is a d-degenerate graph, and r is a request for G with domain of size 1, then (G,L,r) is 1-satisfiable whenever L is a (d+1)-assignment. In this paper, we extend this result to all d for bipartite d-degenerate graphs. The literature on flexible list coloring tends to focus on showing that for a fixed graph G and k ∈ ℕ there exists an ε> 0 such that G is (k, ε)-flexible, but it is natural to try to find the largest possible ε for which G is (k,ε)-flexible. In this vein, we improve a result of Dvořák et al., by showing d-degenerate graphs are (d+2, 1/2d+1)-flexible. In pursuit of the largest ε for which a graph is (k,ε)-flexible, we observe that a graph G is not (k, ε)-flexible for any k if and only if ε> 1/ ρ(G), where ρ(G) is the Hall ratio of G, and we initiate the study of the list flexibility number of a graph G, which is the smallest k such that G is (k,1/ ρ(G))-flexible. We study relationships and connections between the list flexibility number, list chromatic number, list packing number, and degeneracy of a graph.