# Chromatic number of a family of graphs

It is well-known that if a graph has maximum degree $$d$$, then it is $$d+1$$ colorable. Say we have $$d+1$$ graphs $$G_1,\ldots, G_{d+1}$$ on the same vertex set $$V$$, and say each $$G_i$$ has maximum degree at most $$d$$.

A coloring of $$\textbf{G}:=\{G_1,\ldots, G_{d+1}\}$$ is just a labelling of the common vertex set of $$\textbf{G}$$ with $$\{1,\ldots, k\}$$, for some $$k\in\mathbb{N}$$. This coloring is proper if for any $$i\in\{1,\ldots, k\}$$, no edge of $$G_i$$ can be found between two vertices colored $$i$$.

My question is whether $$\textbf{G}$$ admits a proper coloring with just $$d+1$$ labels.

Another way to formulate this is that we are looking for a partition of the common vertex set $$V=V_1\cup \ldots \cup V_{d+1}$$, where $$V_i$$ is an independent set in $$G_i$$.

The simplest case is when $$d=1$$. In this case, $$\textbf{G}=\{G_1, G_2\}$$, and both $$G_1$$ and $$G_2$$ are matchings. I claim that $$\textbf{G}$$ can be properly $$2$$-colored. Proceed with induction - base case is clear. If there exists a vertex that is isolated in $$G_1$$, we can remove that vertex, apply induction, and label that vertex $$1$$. Thus, we can assume every vertex is non-isolated in both $$G_1$$ and $$G_2$$, which is only possible if $$\textbf{G}$$ is an even cycle, its edges alternating between $$G_1$$ and $$G_2$$. It follows that $$\textbf{G}$$ can be properly $$2$$-colored.

• "no edge of $G_i$": do you instead mean "no edge of any $G_j$"? Sep 23 '20 at 14:22
• Correct me if I am wrong, but is your problem equivalent to the following: for each $G_i$ you want to find an independent set $V_i\subseteq V$ ($V$ being the common vertex set), so that $V_1\cup\cdots\cup V_{d+1}=V$. To see the equivalence: interpret the $V_i$ as vertices that are colored with color $i$. We can assume that the $V_i$ are disjoint: if they are not, remove the doubled vertex from one of the problematic sets. Sep 23 '20 at 15:39
• @RobPratt No, I mean no edge of $G_i$ as written. The vertices of the $i^{th}$ label should be an independent set in $G_i$. Sep 23 '20 at 20:27
• @M.Winter That is correct, that's an equivalent formulation. Sep 23 '20 at 20:28