Cooperative colorings of forests

In this paper, all graphs and vertex sets that we consider are finite. Given a family $\mathcal{G}=\{G_{1},\dots,G_{k}\}$ of graphs that span a common vertex set $V$, a cooperative coloring of $\mathcal{G}$ is defined as a family of sets $R_{1},\dots,R_{k}\subseteq V$ such that for each $1\leq i\leq k$, $R_{i}$ is an independent set of $G_{i}$, and $V=\bigcup_{i=1}^{k}R_{i}$. If each graph $G_{i}\in\mathcal{G}$ is equal to a single graph $G$, then the problem of finding a cooperative coloring of $\mathcal{G}$ is equivalent to the problem of finding a proper $k$-coloring of $G$. Hence, in the cooperative coloring problem, the indices of the graphs in $\mathcal{G}$ resemble colors used in the traditional graph coloring problem, and we often refer to the indices of graphs in our family $\mathcal{G}$ as colors.

The cooperative coloring problem is a specific kind of independent transversal problem, which is defined as follows. Given a graph $H$ with a vertex partition $V_{1}\cup\dots\cup V_{r}$, we say that an independent transversal on $H$ is an independent set $I$ in $H$ such that $I$ contains exactly one vertex from each part $V_{i}$. Given a graph family $\mathcal{G}=\{G_{1},\dots,G_{k}\}$ on a common vertex set $V$, we can transform the cooperative coloring problem on $\mathcal{G}$ into an independent transversal problem as follows. We define a graph $H$ with a vertex set $V(H)=V\times[k]$, an edge $(u,i)(v,i)$ for each edge $uv\in E(G_{i})$, and with a vertex partition consisting of a part $\{v\}\times[k]$ for each vertex $v\in V$. Then, given such a graph $H$ constructed from $\mathcal{G}$, an independent transversal on $H$ with respect to the parts described above gives a cooperative coloring of $\mathcal{G}$, and any cooperative coloring of $\mathcal{G}$ can be transformed into an independent transversal on $H$ after possibly deleting extra vertices to make the independent sets $R_{i}$ disjoint. Certain other graph coloring problems can also be naturally described as independent transversal problems. For example, DP-coloring (also called correspondence coloring) is a recent generalization of list coloring invented by Dvořák and Postle [5]. One way of defining the DP-chromatic number $\chi_{DP}(G)$ of a graph $G$ is with the following statement: $\chi_{DP}(G)\leq k$ if and only if every graph $H$ forming a $k$-sheeted covering space of $G$ with a projection $p:H\rightarrow G$ has an independent transversal with respect to the partition $\bigcup_{v\in V(G)}p^{-1}(v)$ of $V(H)$.

The notion of a cooperative coloring can be naturally generalized to the notion of a cooperative list coloring, defined as follows. Consider a graph family $\mathcal{G}=\{G_{1},\dots,G_{k}\}$ in which each graph $G_{i}$ has a vertex set $V_{i}$ that may or may not share vertices with the vertex sets $V_{j}$ of the other graphs $G_{j}\in\mathcal{G}$. We write $V=V_{1}\cup\dots\cup V_{k}$. Then, we say that a cooperative list coloring of $\mathcal{G}$ is a family of vertex subsets $R_{1},\dots,R_{k}$ such that for each value $1\leq i\leq k$, it holds that $R_{i}\subseteq V_{i}$ and $R_{i}$ is an independent set of $G_{i}$, and such that $V=\bigcup_{i=1}^{k}R_{i}$. Every list coloring problem on a graph $G$ with a list function $L$ can be transformed into a cooperative list coloring problem as follows. For each color $c\in\bigcup_{v\in V(G)}L(v)$, we define the graph $G_{c}$ to be the subgraph of $G$ induced by those vertices $v\in V(G)$ for which $c\in L(v)$. Then, finding a list coloring on $G$ is equivalent to finding a cooperative list coloring on the family $\mathcal{G}=\{G_{c}:c\in\bigcup_{v\in V(G)}L(v)\}$. The cooperative list coloring problem can also be transformed into an independent transversal problem in a similar way to the cooperative coloring problem.

One natural question in graph coloring asks for an upper bound on the number of colors needed to color a graph in terms of its maximum degree. Similarly, in the setting of cooperative colorings, we may ask how many graphs of maximum degree $d$ are necessary in a graph family $\mathcal{G}$ on a common vertex set in order to guarantee the existence of a cooperative coloring. A simple argument using the Lovász Local Lemma shows that if each graph in $\mathcal{G}$ is of maximum degree at most $d$, then $\mathcal{G}$ has a cooperative coloring whenever $|\mathcal{G}|\geq 2ed$. A more involved argument of Haxell [8] implies that $\mathcal{G}$ is guaranteed a cooperative coloring whenever $|\mathcal{G}|\geq 2d$. When $d$ is large, Loh and Sudakov [11] have shown that a lower bound of the form $|\mathcal{G}|\geq(1+o(1))d$ also guarantees the existence of a cooperative coloring on $\mathcal{G}$. On the other hand, Aharoni, Holzman, Howard, and Sprüssel [2] have constructed families containing $d+1$ graphs of maximum degree $d$ spanning a common vertex set that do not admit a cooperative coloring.

For a graph class $\mathcal{H}$, Aharoni, Berger, Chudnovsky, Havet, and Jiang [1] defined the parameter $m_{\mathcal{H}}(d)$ to be the minimum value $m$ for which the following holds: If $\mathcal{G}$ is a family of at least $m$ graphs of $\mathcal{H}$ of maximum degree at most $d$ that span a common vertex set, then $\mathcal{G}$ must have a cooperative coloring. When $\mathcal{H}$ is the family of all graphs, they write $m(d)=m_{\mathcal{H}}(d)$. The discussion above implies that $m(d)\leq 2d$ for all values $d\geq 1$, and $m(d)\leq d+o(d)$ asymptotically when $d$ is large. Note that all asymptotics in this paper will be with respect to the parameter $d$, which will always be an upper bound for the maximum degree of each graph in a given graph class.

In a similar fashion to Aharoni, Berger, Chudnovsky, Havet, and Jiang, we will define the parameter $\ell_{\mathcal{H}}(d)$ for a graph class $\mathcal{H}$ as follows. We say $\ell_{\mathcal{H}}(d)$ is the minimum value $\ell$ such that if $\mathcal{G}$ is a family of graphs from $\mathcal{H}$ of maximum degree at most $d$ whose vertex sets are subsets of a universal vertex set $V$, and if each vertex $v\in V$ belongs to at least $\ell$ graphs in $\mathcal{G}$, then $\mathcal{G}$ has a cooperative list coloring. It is straightforward to show that for any graph class $\mathcal{H}$ and for any value $d$, $m_{\mathcal{H}}(d)\leq\ell_{\mathcal{H}}(d)$. When $\mathcal{H}$ is the class of all graphs, we write $\ell(d)=\ell_{\mathcal{H}}(d)$. Haxell’s argument [8] showing $m(d)\leq 2d$ and Loh and Sudakov’s argument [11] showing $m(d)\leq d+o(d)$ were both originally formulated for a more general independent transversal problem, and hence their arguments give the same upper bounds on $\ell(d)$ as well.

We summarize the discussion above with the following inequalities:

In [1], Aharoni, Berger, Chudnovsky, Havet, and Jiang considered the value $m_{\mathcal{F}}(d)$ for the class $\mathcal{F}$ of forests. These authors obtained a lower bound for $m_{\mathcal{F}}(d)$ from a construction and obtained an upper bound for $m_{\mathcal{F}}(d)$ by using a creative application of the Lovász Local Lemma that resembles an earlier method used by Bernshteyn, Kostochka, and Zhu [3, Section 4.2], which involves giving each vertex in the problem a random color inventory and then attempting to greedily give each vertex a color from its inventory. Since the method for obtaining an upper bound on $m_{\mathcal{F}}(d)$ also applies to the cooperative list coloring problem with no changes, we have the following result from [1]:

By using a similar approach involving the Lovász Local Lemma, Bradshaw and Masařík [4] showed that the upper bound in (2) applies not only to forests, but also to graph families of bounded degeneracy $k$ at the expense of a constant factor. In particular, they showed that if $\mathcal{H}$ is the family of $k$-degenerate graphs, then $\ell_{\mathcal{H}}(d)\leq 13(1+k\log(kd))$.

In this paper, we will construct a family of forests which we can use to prove that $m_{\mathcal{F}}(d)\geq(1+o(1))\frac{\log d}{\log\log d}$, improving the lower bound in (2) significantly. One interesting feature of our construction is that each graph in our family is a forest of stars. Hence, we write $\mathcal{S}$ for the class of of star forests, and since $\mathcal{S}\subseteq\mathcal{F}$, we observe that $m_{\mathcal{S}}(d)\leq m_{\mathcal{F}}(d)$. With $\mathcal{S}$ defined, we remark that our construction actually implies the stronger lower bound $m_{\mathcal{S}}(d)\geq(1+o(1))\frac{\log d}{\log\log d}$. With a lower bound for $m_{\mathcal{S}}(d)$ established, it is also natural to ask for an upper bound on $m_{\mathcal{S}}(d)$. We will prove two results that both imply, as a corollary, that $m_{\mathcal{S}}(d)\leq\ell_{\mathcal{S}}(d)\leq(1+o(1))\frac{\log d}{\log\log d}$, and hence, we will conclude that both $m_{\mathcal{S}}(d)$ and $\ell_{\mathcal{S}}(d)$ are of the form $(1+o(1))\frac{\log d}{\log\log d}$.

In this section, we will give a construction that shows that $m_{\mathcal{F}}(d)\geq m_{\mathcal{S}}(d)\geq(1+o(1))\frac{\log d}{\log\log d}$. For ease of presentation, we will work in the setting of adapted colorings, which are defined as follows. Given a multigraph $G$ with a (not necessarily proper) edge coloring $\varphi$, an adapted coloring on $(G,\varphi)$ is a (not necessarily proper) vertex coloring $\sigma$ of $G$ in which no edge $e$ is colored the same color as both of its endpoints $u$ and $v$—that is, $\neg\left(\varphi(e)=\sigma(u)=\sigma(v)\right)$. In other words, if $e\in E(G)$ is a $\mathtt{red}$ edge, then both endpoints of $e$ may not be colored $\mathtt{red}$, but both endpoints of $e$ may be colored, say, $\mathtt{blue}$, and the endpoints of $e$ may also be colored with two different colors. A cooperative coloring problem on a family $\mathcal{G}$ may be translated into an adapted coloring problem by coloring the edges of each graph $G_{i}\in\mathcal{G}$ with the color $i$ and then considering the multigraph obtained from the union of all graphs in $\mathcal{G}$, and an adapted coloring problem may be similarly translated into a cooperative coloring problem. Adapted colorings were first considered by Kostochka and Zhu [10] and have been frequently studied since then [7, 9, 12, 14].

With the adapted coloring framework defined, we are ready to prove our lower bound for $m_{\mathcal{S}}(d)$.

In this section, we aim to show that $\ell_{\mathcal{S}}(d)\leq(1+o(1))\frac{\log d}{\log\log d}$. In order to prove this upper bound, we establish a partition lemma, which essentially shows that if $\mathcal{H}$ is a graph class whose graphs can be vertex-partitioned into members of classes $\mathcal{A}$ and $\mathcal{B}$ for which $\ell_{\mathcal{A}}(d)$ and $\ell_{\mathcal{B}}(d)$ are not too large, then $\ell_{\mathcal{H}}(d)$ is also not too large. While proving the partition lemma, it is essential that we work in the setting of cooperative list colorings rather than the setting of cooperative colorings.

While we can use our partition lemma to prove the upper bound $\ell_{\mathcal{S}}(d)\leq(1+o(1))\frac{\log d}{\log\log d}$ directly, we will see that the lemma gives us stronger results that imply this upper bound on $\ell_{\mathcal{H}}(d)$ as a corollary. We will prove two results that both show an upper bound on $\ell_{\mathcal{H}}(d)$ for some graph class $\mathcal{H}$ based on certain forest structures in the graphs of $\mathcal{H}$, and both of these results will imply that $\ell_{\mathcal{S}}(d)\leq(1+o(1))\frac{\log d}{\log\log d}$.

One tool that we will need to prove the partition lemma is the well-known Lovász Local Lemma, which first appears in a weaker form in [6] and can be found in many textbooks, including for example [13, Chapter 4].

Our partition lemma is as follows.

It may help the reader first to visualize $\mathcal{A}=\mathcal{B}$ as the class of edgeless graphs and to visualize $\mathcal{H}=\mathcal{S}$ as the class of star forests. In this special case, for each star forest $G\in\mathcal{H}$, we may let $A$ denote the leaf set of $G$ and let $B$ denote the set consisting of the centers of the star components of $G$. In this special case, $\ell_{\mathcal{A}}(d)=\ell_{\mathcal{B}}(d)=t=1$, so the lemma immediately implies that $\ell_{\mathcal{S}}(d)\leq(1+o(1))\frac{\log d}{\log\log d}$.

As mentioned before, we can use Lemma 3.2 directly to prove that $\ell_{\mathcal{S}}(d)\leq(1+o(1))\frac{\log d}{\log\log d}$, which shows that the lower bound in Theorem 2.1 is best possible up to the $o(1)$ function. We will see that Lemma 3.2 also implies much stronger results, and we will prove two such results that both imply this upper bound on $\ell_{\mathcal{S}}(d)$ as a corollary.

For the first of our results, we will need some definitions. Given a rooted tree $T$ with a root $r$, the height of a vertex $v$ in $T$ is the distance from $v$ to $r$, and the height of $T$ is the maximum height achieved over all vertices $v\in V(T)$. Given integers $q\geq 1$ and $h\geq 1$, a $q$-ary tree of height $h$ is a rooted tree in which every vertex of height at most $h-1$ has exactly $q$ children. Given an integer $k\geq 1$, we write $\log^{(k)}d=\underbrace{\log\log\dots\log}_{\text{$k$ times}}d$. Then, we have the following result.

To use Theorem 3.3 to prove that $\ell_{\mathcal{S}}(d)\leq(1+o(1))\frac{\log d}{\log\log d}$, consider a binary tree of height $2$, which has $7$ vertices and $4$ leaves. Since no star forest contains this binary tree as a subgraph, the upper bound on $\ell_{\mathcal{S}}(d)$ follows from Theorem 3.3 with $q=h=2$.

Next, we show that if $\mathcal{H}$ is a graph class whose graphs have a certain quotient of bounded treedepth, then $\ell_{\mathcal{H}}(d)$ can be bounded above. For this next theorem, we will need some more definitions. If $G$ is a graph and $U_{1},\dots,U_{k}$ is a partition of $V(G)$, then the quotient graph $G/(U_{1},\dots,U_{k})$ is the graph on $k$ vertices obtained by contracting each part $U_{i}$ to a single vertex and deleting all resulting loops and parallel edges.

Given a rooted tree $T$ with a root $r$, we define the closure of $T$ as the graph on $V(T)$ in which two vertices $u,v\in V(T)$ are adjacent if and only if $u$ and $v$ form an ancestor-descendant pair. Given a rooted forest $F$, in which each tree component has a root, the closure of $F$ is the union of the closures of the components of $F$. For a graph $G$, if there exists a rooted tree $T$ of height $h-1$ such that $G$ is a subgraph of the closure of $T$, then we say that the treedepth of $G$ is at most $h$. The reason for this “off-by-one error” is that if $T$ has height $h-1$, then the longest path in $T$ with the root as an endpoint contains exactly $h$ vertices.

With these definitions in place, we are ready for our second theorem implying that $\ell_{\mathcal{S}}(d)\leq(1+o(1))\frac{\log d}{\log\log d}$.

In order to use Theorem 3.4 to prove that $\ell_{\mathcal{S}}(d)\leq(1+o(1))\frac{\log d}{\log\log d}$, we observe that if $G$ is a star forest, then every component of $G$ has treedepth at most $2$, so we can apply Theorem 3.4 with $h=2$ and obtain the upper bound.

By combining (2) and Theorem 2.1, we obtain the following inequality:

While this inequality is certainly much tighter than (2), the correct asymptotic growth rates for $m_{\mathcal{F}}(d)$ and $\ell_{\mathcal{F}}(d)$ remain open. While we do not have a conjecture for the correct growth rates of these quantities, we remark that if $m_{\mathcal{F}}(d)=\Theta(\log d)$, then Theorem 3.3 gives a strong necessary condition for forest families that demonstrate this growth rate. Namely, suppose that $\{\mathcal{G}_{d}\}_{d\geq 1}$ is a sequence of forest families such that $|\mathcal{G}_{d}|=\Theta(\log d)$, the forests of $\mathcal{G}_{d}$ have maximum degree at most $d$, and $\mathcal{G}_{d}$ has no cooperative coloring. Then, Theorem 3.3 implies that for each finite tree $T$, $T$ must appear as a subgraph of infinitely many forests from the families in $\{\mathcal{G}_{d}\}_{d\geq 1}$.