Separating the online and offline DP-chromatic numbers

We will consider several graph coloring problems. In the list coloring problem, we have a graph $G$ and a list $L(v)$ of colors at each vertex $v\in V(G)$. In this setting, we say that an $L$-coloring of $G$ is a proper coloring $\varphi:V(G)\rightarrow\bigcup_{v\in V(G)}L(v)$ of $G$ in which $\varphi(v)\in L(v)$ for every vertex $v\in V(G)$. If $G$ always has an $L$-coloring whenever $|L(v)|=f(v)$ for each vertex $v\in V(G)$, then we say that $G$ is $f$-choosable. If $f$ is a constant function $f(v)=k$, then we say that the list-chromatic number (or choosability) of $G$ is at most $k$, and we write $\operatorname{\chi_{\ell}}(G)\leq k$.

The DP-coloring problem is a generalization of the list coloring problem introduced by Dvořák and Postle [3], defined as follows. Given a graph $G$ and a function $f:V(G)\rightarrow\mathbb{N}$, an $f$-fold cover of $G$ is a graph $H$ obtained by the following process:

• •

  For each vertex $v\in V(G)$, add a clique $K_{f(v)}$ to $H$, and write $L(v)$ for the vertex set of this clique.

• •

  For each edge $uv\in E(G)$, add a matching between $L(u)$ and $L(v)$.

Then, we say that an independent set in $H$ of size $|V(G)|$ is a DP-coloring of $G$ with respect to $H$. If $G$ always has a DP-coloring for every $f$-fold cover $H$ of $G$, then we say that $G$ is DP-$f$-colorable. If $f$ is a constant function $f(v)=k$, then we say that $H$ is a $k$-fold cover of $G$, and if $G$ always has a DP-coloring for every $k$-fold cover $H$ of $G$, then we say that the DP-chromatic number of $G$ is at most $k$, and we write $\chi_{DP}(G)\leq k$. Given a cover $H$ of $G$, we often refer to the vertices of $H$ as colors, and if $c\in L(v)$ for a vertex $v\in V(G)$, then we say that the color $c$ is above $v$. Note that when $f(v)=k$ is a constant function, if the cliques in $H$ corresponding to vertices in $G$ are replaced with independent sets, and if each matching between sets $L(u)$ and $L(v)$ is a perfect matching, then $H$ is a $k$-sheeted covering space of $G$, and a DP-coloring of $G$ is equivalent to an independent transversal of the fibers in $H$ above the vertices of $G$ (see [4] for an introduction to graphs as topological spaces).

Every list-coloring problem can be transformed into a DP-coloring problem as follows. Given a graph $G$ with a color list $L^{\prime}(v)$ at every vertex $v\in V(G)$, we construct a cover $H$ of $G$ by adding a clique with vertex set $L(v)$ for every vertex $v\in V(G)$, with elements of $L(v)$ corresponding to colors in $L^{\prime}(v)$. Then, we consider each edge $uv\in E(G)$, and we add an edge in $H$ between each pair $(c,c^{\prime})\in L(u)\times L(v)$ for which $c$ and $c^{\prime}$ both correspond to a common color from $L^{\prime}(u)\cap L^{\prime}(v)$. When $H$ is constructed this way, a DP-coloring of $G$ with respect to $H$ is equivalent to an $L^{\prime}$-coloring of $G$. Therefore, it holds that $\operatorname{\chi_{\ell}}(G)\leq\chi_{DP}(G)$.

We will also consider two online graph coloring problems. The online DP-coloring problem takes place in the form of a DP-coloring game between two players, called Lister and Painter. The game is played on a graph $G$ with a function $f:V(G)\rightarrow\mathbb{N}$. At the beginning of the game, each vertex $v\in V(G)$ has $f(v)$ tokens. On each turn $i$, Lister removes some number $m_{i}(v)$ (possibly zero) of tokens from each vertex $v\in V(G)$ and then reveals a clique $K_{m_{i}(v)}$ above each vertex $v$. Furthermore, for each edge $uv\in E(G)$, Lister reveals a matching between the revealed cliques above $u$ and $v$. The cliques and matchings revealed on this turn $i$ form a cover $H_{i}$ of $G$. After $H_{i}$ is revealed, Painter chooses an independent set from the vertices of $H_{i}$. The game ends when $G$ has no more tokens for Lister to remove. Painter wins the game if she manages to choose at least one color above each vertex of $G$ before the game is over; otherwise, Lister wins. If Painter always has a winning strategy in the DP-coloring game on a graph $G$ when each vertex $v\in V(G)$ begins with $k$ tokens, then we say that the online DP-chromatic number (or DP-paintability) of $G$ is at most $k$, and we write $\chi_{DPP}(G)\leq k$. Observe that if each vertex of $G$ begins with $k$ tokens, then Lister has the option of revealing a $k$-fold cover $H$ of $G$ on the first turn and asking Painter to find a DP-coloring of $G$ with respect to $H$, and therefore $\chi_{DP}(G)\leq\chi_{DPP}(G)$.

If, in the DP-coloring game, Lister is only allowed to remove at most one token from each vertex of $G$ during each turn and must always reveals edges wherever possible, then we call this variant of the game the list-coloring game. For the list-coloring game, we may equivalently imagine that on each turn $i$, Lister reveals a single color $c_{i}$ above each vertex of some induced subgraph $G^{\prime}_{i}$ of $G$, and Painter must choose some independent set $I_{i}$ of $G^{\prime}_{i}$ and color each vertex in $I_{i}$ with $c_{i}$. In this equivalent setting, each vertex $v\in V(G)$ still begins with $f(v)$ tokens, and a single token is removed from $v$ whenever Lister reveals a color above $v$. In this setting, Painter wins the game if and only if she can color every vertex of $G$ before the game ends. If Painter always has a strategy to win the list-coloring game on a graph $G$ when each vertex $v\in V(G)$ begins with $f(v)$ tokens, then we say that $G$ is $f$-paintable. If $f$ is a constant function $f(v)=k$, then we say that $G$ is $k$-paintable, and we write $\chi_{P}(G)\leq k$. The online list-coloring game was originally invented using this framework of revealing colors above vertices independently by Schauz [7] and Zhu [8].

At the end of the list-coloring game on $G$ with a constant function $f(v)=k$, the colors revealed at each vertex $v$ form a set $L(v)$ of $k$ colors, and if Painter wins the game, then Painter completes a proper $L$-coloring of $G$. Since Lister is free to form any list assignment $L$ on the vertices of $G$, it follows that if $G$ is $k$-paintable, then $G$ is also $k$-choosable, and hence $\chi_{\ell}(G)\leq\chi_{P}(G)$. Also, since the online list-coloring game is at least as difficult for Lister as the DP-coloring game, it also follows that $\chi_{P}(G)\leq\chi_{DPP}(G)$.

After putting all of the inequalities between these parameters together, we obtain two inequality chains:

	$\displaystyle\chi_{\ell}(G)\leq$	$\displaystyle\chi_{DP}(G)$	$\displaystyle\leq\chi_{DPP}(G);$
	$\displaystyle\chi_{\ell}(G)\leq$	$\displaystyle\chi_{P}(G)$	$\displaystyle\leq\chi_{DPP}(G).$

Given these inequality chains, it is natural to ask whether the differences between adjacent parameters can be arbitrarily large. For three out of these four differences, we find an affirmative answer by letting $G=K_{n,n}$. Indeed, Bernshteyn [1] showed that a graph $G$ of average degree $d$ satisfies $\chi_{DP}(G)=\Omega\left(\frac{d}{\log d}\right)$, implying that $\chi_{DP}(K_{n,n})=\Omega\left(\frac{n}{\log n}\right)$. Since it is known that $\chi_{\ell}(K_{n,n})\leq\chi_{P}(K_{n,n})=\log_{2}n+O(1)$ [2], this shows that

$$\chi_{DP}(K_{n,n})-\chi_{\ell}(K_{n,n})=\Omega\left(\frac{n}{\log n}\right)\textrm{ \indent and \indent}\chi_{DPP}(K_{n,n})-\chi_{P}(K_{n,n})=\Omega\left(\frac{n}{\log n}\right).$$

Duraj, Gutowski, and Kozik [2] also showed that

$$\chi_{P}(K_{n,n})-\chi_{\ell}(K_{n,n})=\Omega(\log\log n).$$

Therefore, by letting $G=K_{n,n}$, we achieve an arbitrarily large difference for each adjacent pair of parameters except for $\chi_{DPP}(G)-\chi_{DP}(G)$. For this final difference, Kim, Kostochka, Li, and Zhu [5] showed there exist graphs $G$ for which $\chi_{DPP}(G)-\chi_{DP}(G)\geq\chi_{P}(G)-\chi_{DP}(G)\geq 1$, implying that this final difference can be positive. However, it has not been shown that this difference can be arbitrarily large.

In this note, we will show that the difference $\chi_{DPP}(G)-\chi_{DP}(G)$ can also be arbitrarily large, answering a question of Kim, Kostochka, Li, and Zhu [5]. Rather than choosing $G=K_{n,n}$, we will construct a graph $G_{t}$ for each $t\geq 1$ that satisfies $\chi_{DPP}(G_{t})-\chi_{DP}(G_{t})\geq t$. We construct our graphs $G_{t}$ by generalizing an idea from the original paper of Kim, Kostochka, Li, and Zhu [5]. Our graphs $G_{t}$ will also satisfy the additional property that $\chi_{P}(G_{t})-\chi_{DP}(G_{t})\geq t$. By combining this equality with the already-known estimate $\chi_{DP}(K_{n,n})-\chi_{P}(K_{n,n})=\Omega\left(\frac{n}{\log n}\right)$, we hence see that the difference $\chi_{DP}(G)-\chi_{P}(G)$ can achieve both positive and negative values of arbitrarily large magnitude.

For each integer $t\geq 1$, we will construct a graph $G_{t}$ that satisfies $\chi_{P}(G_{t})-\chi_{DP}(G_{t})\geq t$. Since $\chi_{DPP}(G)\geq\chi_{P}(G)$ for all graphs $G$, our graphs $G_{t}$ will also satisfy $\chi_{DPP}(G_{t})-\chi_{DP}(G_{t})\geq t$. Our construction is based on a generalization of an idea of Kim, Kostochka, Li, and Zhu [5].

As we are concerned with showing that the paintability of each graph $G_{t}$ is large enough, we begin with an observation about the online list-coloring game. If Lister and Painter play the online list-coloring game on a graph $G$ with some initial token assignment, then Lister wins if and only if he can reach a position in which each uncolored vertex $v\in V(G)$ has some $g(v)$ remaining tokens, and the uncolored subgraph of $G$ is not $g$-choosable. In the original paper of Kim, Kostochka, Li, and Zhu [5], the authors take advantage of this idea in order to construct a graph $G$ satisfying $\chi_{P}(G)\geq\chi_{DP}(G)+1$. In order to show that their graph $G$ has a large enough paintability, these authors show that in the online list-coloring game on their graph $G$, Lister always has a strategy to create an uncolored $K_{1,k}$ subgraph of $G$ in which each leaf $\ell$ has $g(\ell)=1$ token and the center vertex $v$ has $g(v)=k$ tokens. Since $K_{1,k}$ is not $g$-choosable, it follows that Lister has a strategy to win the online list-coloring game on their graph $G$.

In our construction, we will use a similar idea. We first fix the value $k=2^{8t^{3}}$. (With more careful calculation, our proof would work with a smaller value of $k$, but we use this larger value for clearer presentation.) In each of our graphs $G_{t}$, we will show that Lister can always create an uncolored $K_{t,k^{t}}$ subgraph in which each $t$-degree vertex $u$ has $g(u)=t$ tokens and each $k^{t}$-degree vertex $v$ has $g(v)=k$ tokens. The following lemma shows that if Lister manages to create such a subgraph of $G_{t}$, then Lister wins the online list-coloring game.

The most important piece of our construction of $G_{t}$ will be the following gadget $H_{t}$. We construct our gadget $H_{t}$ along with a function $h:V(H_{t})\rightarrow\mathbb{N}$ as follows. We let $H_{t}$ contain $(t+1)k^{t}$ copies $K^{1},\dots,K^{(t+1)k^{t}}$ of the clique $K_{t+1}$, and we write $u^{\ell}_{1},\dots,u^{\ell}_{t+1}$ for the vertices of each clique $K^{\ell}$. We write $U$ for the set of all of these vertices of the form $u_{j}^{\ell}$; in other words, we let $U$ consist of all vertices that we have introduced so far. Then, for each value $1\leq j\leq t+1$, we add $t$ independent vertices $x_{j}^{1},\dots,x_{j}^{t}$, and we make each of these vertices adjacent to $u^{1}_{j},u^{2}_{j},\dots,u^{(t+1)k^{t}}_{j}$. We write $X$ for the set consisting of all of these vertices of the form $x_{j}^{i}$. For each vertex $u_{j}^{\ell}\in U$, we let $h(u_{j}^{\ell})=t+1$, and for each vertex $x_{j}^{i}\in X$, we let $h(x_{j}^{i})=k-t+1$. We now prove two lemmas that show that under appropriate circumstances, winning the online list-coloring game on $H_{t}$ as Painter is much harder than finding a DP-coloring on $H_{t}$.

Now, we construct our graph $G_{t}$. First, we make $k^{k-2t}$ copies of the graph $H_{t}$, and we index them by the $(k-2t)$-tuples in $[k]^{k-2t}$. We also add $k-2t$ vertices $y_{1},\dots,y_{k-2t}$ that are adjacent to all vertices of $U$ in each copy of $H_{t}$. We write $\tilde{U}$ for this set of neighbors of $y_{1},\dots,y_{k-2t}$, that is, the set of vertices belonging to a set $U$ in some copy of $H_{t}$. The following two theorems show that $\chi_{P}(G_{t})-\chi_{DP}(G_{t})\geq t$.

While we have shown for each $t\geq 1$ the existence of a graph $G_{t}$ for which $\chi_{P}(G_{t})-\chi_{DP}(G_{t})\geq t$, it is still open whether there exists a sequence $\{G_{t}\}_{t\geq 1}$ of graphs for which

$$\lim_{t\rightarrow\infty}\frac{\chi_{DPP}(G_{t})}{\chi_{DP}(G_{t})}>1\textrm{ \indent or \indent}\lim_{t\rightarrow\infty}\frac{\chi_{P}(G_{t})}{\chi_{\ell}(G_{t})}>1.$$

On the other hand, it is unknown whether $\chi_{P}(G)$ can be bounded above by a linear or even polynomial function of $\chi_{\ell}(G)$, and it is unknown whether $\chi_{DPP}(G)$ can be bounded above by a linear function of $\chi_{DP}(G)$. Duraj, Gutowski, and Kozik [2] have pointed out that currently, the best known bound for $\chi_{P}(G)$ in terms of $\chi_{\ell}(G)$ comes from the relationship between a graph’s choosability and minimum degree. Namely, a result of Saxton and Thomason [6] states that a graph $G$ of minimum degree $\delta$ satisfies $\chi_{\ell}(G)\geq(1+o(1))\log_{2}\delta$. Writing $d$ for the degeneracy of a graph $G$, we observe that $G$ must have a subgraph of minimum degree $d$, and hence we may use this result to observe that

$$\chi_{P}(G)\leq d+1\leq 2^{(1+o(1))\chi_{\ell}(G)}.$$

For $\chi_{DPP}(G)$, we may use a result of of Bernshteyn showing that a graph $G$ of minimum degree $\delta$ satisfies $\chi_{DP}(G)\geq\frac{\delta/2}{\log(\delta/2)}$ in order to bound $\chi_{DPP}(G)$ in terms of $\chi_{DP}(G)$ in a similar way. Using the same observation as above, if $d$ is the degeneracy of $G$, then

$$\chi_{DPP}(G)\leq d+1\leq(2+o(1))\chi_{DP}(G)\log\chi_{DP}(G).$$

It is likely that a deeper understanding of these coloring parameters is necessary to determine tight bounds between them.

I am grateful to Alexandr Kostochka for offering helpful feedback on an earlier version of this paper.