Codegree Thresholds for $\lambda$-Choosability of Graphs

Abstract

Let $\lambda =\{k_1,\dots ,k_q\}$ be a partition, and let $|\lambda |=k_1+\cdots +k_q$. A $|\lambda |$-list assignment $L$ of a graph $G$ is a $\lambda$-assignment if its color set can be partitioned into $q$ disjoint sets $X_1,\dots ,X_q$ such that $|L(v)\cap X_i|=k_i$ for every vertex $v$ and every $i\in [q]$. This notion, introduced by Zhu [J. Combin. Theory Ser. B, 2020], puts ordinary coloring and list coloring in the same framework. A theorem of Alon [Random Structures Algorithms, 2000] states that every graph with minimum degree $d$ has choice number at least $(1/2-o(1)){\log }_{2}d$. Saxton and Thomason [Invent. Math., 2015] later used the hypergraph container method to replace $1/2$ by the sharp constant $1$. It is natural to ask whether a similar phenomenon holds for every fixed partition $\lambda$. Minimum degree alone is not sufficient: balanced complete bipartite graphs have arbitrarily large minimum degree but are always $\{1,1\}$-choosable. We show that the appropriate replacement is the minimum $q$-codegree, defined for $|V(G)|\ge q$ by ${\delta }_q(G)=\min \{|N_G(S)|:S\subseteq V(G),|S|=q\}$. More precisely, for every partition $\lambda$ there exists an integer $d$ such that every graph $G$ with ${\delta }_q(G)\ge d$ is not $\lambda$-choosable. Let $f(\lambda )$ be the least such $d$. For every fixed $q$, we prove $f(\lambda )\le 2^{(2q+o(1))|\lambda |}$ as $|\lambda |\to \infty$, while $f(\lambda )\ge (q+1{)}^{-1}(1+1/q{)}^{|\lambda |}$ for every $\lambda$. For the partition $\{k,\dots ,k\}$ with $q$ equal parts, we determine the threshold asymptotically: $f(\{k,\dots ,k\})={\rho }_q^{-(1+o(1))k}$ as $k\to \infty$, where ${\rho }_q$ is the unique $x\in (0,1)$ satisfying $x=(1-x{)}^q$. When $q=1$, our result implies $\mathrm{ch}(G)\ge (1-o(1)){\log }_2\delta (G)$.

28 pages