2024/02/15 by Dan Hefetz, Michael Krivelevich, Hefetz, Dan +1
Chemistry · Computer Science · Physics and Astronomy · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #History and advancements in chemistry
paper · pdf · doi:10.48550/arxiv.2402.09998
openalex publication_date 2024/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given positive integers k ≤ m and a graph G, a family of lists L = \L(v) : v ∈ V(G)\ is said to be a random (k,m)-list-assignment if for every v ∈ V(G) the list L(v) is a subset of \1, …, m\ of size k, chosen uniformly at random and independently of the choices of all other vertices. An n-vertex graph G is said to be a.a.s. (k,m)-colourable if limn → ∞ ℙ(G \textrm is L-colourable) = 1, where L is a random (k,m)-list-assignment. We prove that if m ≫ n1/k2 Δ1/k and m ≥ 3 k2 Δ, where Δ is the maximum degree of G and k ≥ 3 is an integer, then G is a.a.s. (k,m)-colourable. This is not far from being best possible, forms a continuation of the so-called palette sparsification results, and proves in a strong sense a conjecture of Casselgren. Additionally, we consider this problem under the additional assumption that G is H-free for some graph H. For various graphs H, we estimate the smallest m for which an H-free n-vertex graph G is a.a.s. (k,m)-colourable. This extends and improves several results of Casselgren.