3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ "no edge of $G_i$": do you instead mean "no edge of any $G_j$"? $\endgroup$
    – RobPratt
    Sep 23 '20 at 14:22
  • $\begingroup$ 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. $\endgroup$
    – M. Winter
    Sep 23 '20 at 15:39
  • $\begingroup$ @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$. $\endgroup$
    – alpmu
    Sep 23 '20 at 20:27
  • $\begingroup$ @M.Winter That is correct, that's an equivalent formulation. $\endgroup$
    – alpmu
    Sep 23 '20 at 20:28
4
$\begingroup$

The concept you introduce is called a cooperative coloring. Check out, e.g., this paper. Theorem 1 (with a reference to another paper) claims a negative answer to your question; but there is other information you may find relevant.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.