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.
