Source-linked AI summary
The asymptotic behavior of the correspondence chromatic number
Anton Bernshteyn
TL;DR
The paper studies correspondence coloring, a generalization of list coloring, and establishes bounds on its chromatic number. Its results include an average-degree lower bound and a triangle-free upper bound analogous to Johansson’s list-coloring result; together, they imply a constant-factor characterization by degree for regular triangle-free graphs.
Problem
The paper asks how the correspondence chromatic number relates to graph degree, extending the study of degree-based bounds for list coloring.
Source: §1 · pp. 1–2Method
The paper proves an average-degree lower-bound result and adapts Johansson’s proof for triangle-free graphs, modifying technical features for correspondence coloring.
Source: §1 · p. 2Results
For triangle-free graphs, correspondence coloring has the same O(Δ/ln Δ) upper-bound form as Johansson’s list-coloring result, and regular triangle-free graphs have correspondence chromatic number determined by degree up to a constant factor.
Source: §1 · pp. 2–3Takeaways & Limitations
For regular triangle-free graphs, degree determines the correspondence chromatic number up to a constant factor.
Source: §1 · p. 3The triangle-free upper-bound proof is set up for graphs of maximum degree at most Δ with uniform lists of size ceil(120Δ/ln Δ).
Source: §3.4.2 · p. 9, §3.5 · p. 14
Abstract
from arXiv · showhide
Alon proved that for any graph $G$, $\chi_\ell(G) = \Omega(\ln d)$, where $\chi_\ell(G)$ is the list chromatic number of $G$ and $d$ is the average degree of $G$. Dvo\v{r}\'{a}k and Postle recently introduced a generalization of list coloring, which they called correspondence coloring. We establish an analogue of Alon's result for correspondence coloring; namely, we show that $\chi_c(G) = \Omega(d/\ln d)$, where $\chi_c(G)$ denotes the correspondence chromatic number of $G$. We also prove that for triangle-free $G$, $\chi_c(G) = O(\Delta/\ln \Delta)$, where $\Delta$ is the maximum degree of $G$ (this is a generalization of Johansson's result about list colorings). This implies that the correspondence chromatic number of a regular triangle-free graph is, up to a constant factor, determined by its degree.
1 Introduction
The introduction defines list and correspondence coloring, then presents lower- and upper-bound results for correspondence chromatic number. For regular triangle-free graphs, the degree determines that number up to a constant factor.
1 Introduction
- Correspondence coloring generalizes list coloring, and its chromatic number can exceed the list chromatic number; for even cycles the two values are 3 and 2, respectively.The correspondence chromatic number is defined through color covers, while list coloring assigns available color sets to vertices.Source: §1 · pp. 1–2
- The first result gives a correspondence-chromatic lower bound in terms of average degree, growing faster than the list-chromatic lower bound and remaining only a logarithmic factor from the trivial upper bound for regular graphs.The passage describes this result as an analogue of Alon's theorem.Source: §1 · p. 2
- For triangle-free graphs, the paper establishes a correspondence-coloring upper bound analogous to Johansson’s list-coloring bound of O(Δ/ln Δ).The result is presented as extending Johansson’s bound from list coloring to correspondence coloring.Source: §1 · pp. 2–3
- For regular triangle-free graphs, the degree determines the correspondence chromatic number up to a constant factor.The paper derives this conclusion by combining its lower- and upper-bound results.Source: §1 · p. 3
2 Proof of Theorem 1.6
The proof constructs a random cover by independently choosing a perfect matching between the lists of each adjacent vertex pair. A union bound shows that some such cover is not colorable when k ln k < d/2.
2 Proof of Theorem 1.6
- For each edge uv, the proof independently joins L(u) and L(v) by a uniformly random perfect matching to form a cover.Each vertex receives a list of size k.Source: §2 · p. 3
- For any fixed choice of one color per vertex, the probability it is a proper coloring is at most e^(-|E(G)|/k).Each edge has probability 1 − 1/k of avoiding a matched pair.Source: §2 · p. 3
- The probability that any coloring exists is less than 1 when k ln k < d/2, so a non-colorable cover exists.The proof reduces this condition to k ln k < |E(G)|.Source: §2 · p. 3
3 Proof of Theorem 1.7
The section states an explicit form of Theorem 1.7 for triangle-free graphs with bounded maximum degree. Its proof follows Johansson’s approach with adjustments for correspondence coloring, including a significantly different proof of one lemma.
3 Proof of Theorem 1.7
- Theorem 1.7′ is stated for triangle-free graphs whose maximum degree is at most Δ, for sufficiently large Δ.The statement is presented as an explicit form of Theorem 1.7.Source: §3 · p. 3
- The proof largely adapts Johansson’s proof for ordinary graph coloring, with technical adjustments for correspondence coloring.The proof uses the version in Chapter 13 of.Source: §3 · p. 3
- The proof of Lemma 3.24 is the one significantly different step, because the approach of cannot be directly adapted.Source: §3 · p. 3
3.1 Outline of the proof
For sufficiently large maximum degree, the proof seeks a correspondence coloring by repeatedly reducing degrees while controlling color probabilities and vertex entropy. The process aims to reach a nice tuple, which yields a coloring.
3.1 Outline of the proof
- The outline assumes Δ is sufficiently large and fixes list size k = ⌈120Δ/ln Δ⌉ in the reduct lemmas.The probability assignment also requires each p(x) to be zero or at least 1/k.Source: §3.1 · pp. 4–5
- A nice tuple yields a p-moderate (L, H)-coloring, and the outline reduces the theorem to finding suitable reducts.The reduct construction is iterated until a nice tuple is obtained.Source: §3.1 · pp. 4–5
- A reduct preserves the original lists on an induced subgraph and is designed so that its moderate colorings extend to the original graph.This extension property allows successive reduct steps to be composed.Source: §3.1 · pp. 4–5
- The method assigns nonnegative weights p to cover vertices and uses entropy to control the difference between p(v) and its mean pm(v).The outline introduces entropy as a per-vertex quantity associated with the cover and probability assignment.Source: §3.1 · p. 5
- The core reduct step lowers degrees while approximately preserving vertex and edge probabilities and vertex entropy.The stated conditions include p(v) ≈ 1, p(uv) = O(1/k), and Q(v) = Ω(ln Δ).Source: §3.1 · p. 5
- Each reduct retains entropy at least Q(v) − 2 deg_G(v)/(k ln Δ) − ln Δ · Δ^(-1/6) per vertex.The degree bound becomes deg_G′(v) ≤ deg_G(v) · (1 − 2/(3 ln Δ)) + Δ^(2/3).Source: §3.1 · p. 5
3.2 Proof of Lemma 3.2
The proof turns correspondence coloring into avoiding a family of forbidden partial choices. A probabilistic choice-function theorem supplies the avoidance step used to obtain an (L, H)-coloring.
3.2 Proof of Lemma 3.2
- Lemma 3.2 is obtained as an immediate corollary of a result proved in [4].A similar result can also be obtained using the Lovász Local Lemma.Source: §3.2 · pp. 6–7
- A choice function selects exactly one element from each of a collection of pairwise disjoint sets, while a partial choice function selects at most one.A choice function avoids a partial choice function when it does not contain it.Source: §3.2 · p. 6
- Theorem 3.9 [4] guarantees a choice function avoiding all forbidden partial choices when the stated defect conditions hold.Source: §3.2 · p. 6
- The proof represents each edge xy of H by the forbidden partial choice {x, y}; avoiding all such pairs is an (L, H)-coloring.Source: §3.2 · p. 6
- The proof forms a random set M by independently including each x with probability 2p(x)/δ, then applies the avoidance theorem.Source: §3.2 · p. 6
- A choice function avoiding the edge-pair constraints establishes that G is (L, H)-colorable.Source: §3.2 · p. 6
3.3 Proof of Lemma 3.7
The proof of Lemma 3.7 treats triangle-free graphs of maximum degree at most ∆ with lists of size ⌈120∆/ln ∆⌉, under a restriction on the p-values.
3.3 Proof of Lemma 3.7
- The setup takes a triangle-free graph of maximum degree at most ∆ and lists of size ⌈120∆/ln ∆⌉.Source: §3.3 · p. 7
- For each x in V(H), the stated condition requires p(x)=0 or p(x)≥1/k.Source: §3.3 · p. 7
- The proof seeks an upper bound on |L(v) ∩ B|·p-hat before deriving a lower bound.Source: §3.3 · p. 7
3.4 Proof of Lemma 3.8
The proof repeatedly reduces the coloring instance through a randomized procedure, analyzes the resulting quantities, and uses the lemma’s bounds to complete the reduction step.
3.4.1 The algorithm
- The procedure samples S from colors outside B and defines p′ according to whether a color has a neighbor in S, producing a reduct of the original tuple.The procedure always outputs a reduct, and each p′(x) is either zero or at least p(x).Source: §3.4.1 · p. 8
3.4.2 Analysis of the algorithm
- The analysis uses concentration bounds and the Lovász Local Lemma to control p′-values, entropy, and degrees in the reduced graph.For triangle-free G, the stated analysis uses disjoint neighborhoods of colors across adjacent lists and bounds the probability of saturated colors.Source: §3.4.2 · pp. 9–10
3.4.3 Completing the proof of Lemma 3.8
- Lemma 3.8 gives a reduct whose vertex degrees satisfy deg_G′(v) ≤ deg_G(v)·(1−2/(3 ln ∆))+∆^2/3.It also bounds Q′(v) below by Q(v)−2 deg_G(v)/(k ln ∆)−ln ∆·∆^-1/6, while retaining the condition p′(x)=0 or p′(x)≥1/k.Source: §3.4.3 · pp. 13–14
3.5 Finishing the proof of Theorem 1.7
Repeated applications of Lemma 3.8 produce a nice reduct, whose moderate coloring extends to a coloring of the original graph.
3.5 Finishing the proof of Theorem 1.7
- After i* = O(ln ∆ ln ln ∆) applications of Lemma 3.8, the resulting tuple is nice.Source: §3.5 · pp. 14–15
- A p′′-moderate coloring of the nice reduct extends to a p-moderate coloring of G, so G is (L,H)-colorable.Source: §3.5 · p. 15