# Reduction variation for the q-coloring problem

I'm trying to prove that $q$-COL $\leq^P_m q$-COL$_{2q-1}$, where $q$-COL$_{2q-1}$ is the restriction of the q-coloring problem to graphs of maximum degree $2q-1$. Now, it seems fairly obvious "if you can color a graph of any maximum degree with $q$ colours, then you can colour a graph of maximum degree $2q-1$ with $q$ colours", the second is a subset of the first. Am I correct this far?

Assuming the previous assumption is correct, I need to find a function or mapping from $G$ to $G'$. It would seem that I need to pick a vertex $v \in G$, and $v' \in G'$ and colour $v'$ the same as $v$, then follow the pattern of $v$, for up to $2q-1$ connections, and then leave the rest alone.

In my head this works, but I'm fully new in reductions and would appreciate your input about this. I'd also appreciate any pointers on how to formalise it. Thank you!

• Your "fairly obvious" statement is correct but it has the reduction the wrong way around. You're supposed to be showing that, if you had an algorithm to $q$-colour graphs of max degree $2q-1$, you'd have an algorithm for $q$-colouring arbitrary graphs. Mar 10, 2016 at 16:38
• Thank you for this, there is something in the notation of reductions that always gets me confused!
– Sara
Mar 10, 2016 at 17:24

When proving that $q\text{-}\textsf{COL} \leq_m^P q\text{-}\textsf{COL}_{2q-1}$, what you are really showing is that checking whether a graph with maximal degree $2q-1$ is $q$-colorable isn't any easier than checking whether an arbitrary graph is $q$-colorable. Why is this an interesting statement? Since if we replace $2q-1$ with a small enough number, then checking whether a graph is $q$-colorable does become easier. For example, any graph with maximal degree $q-1$ is $q$-colorable, so checking whether such a graph is $q$-colorable is easy, whereas checking whether an arbitrary graph is $q$-colorable is NP-hard for all $q \geq 3$.
How do you show that $q\text{-}\textsf{COL} \leq_m^P q\text{-}\textsf{COL}_{2q-1}$? You need to transform a given graph $G$ to a graph $H$ with maximum degree $2q-1$ such that $H$ is $q$-colorable iff $G$ is $q$-colorable. The most natural way of doing this is by splitting high-degree vertices. I'll illustrate how to do it for the case $q=2$ (which in reality isn't so interesting — why?), and will let you generalize the construction. Once you do that, you'll also see where $2q-1$ is coming from.
Suppose therefore that $q = 2$. First of all, we number the neighbors of all vertices. For each edge $(v,w)$, there are numbers $i,j$ such that $w$ is the $i$th neighbor of $v$, and $v$ is the $j$th neighbor of $w$. Now, we replace each vertex $v$ of degree $d$ with a path $v_0,\ldots,v_{2d}$, and connect $v_{2i}$ and $w_{2j}$ if $w$ is the $i$th neighbor of $v$ and $v$ is the $j$th neighbor of $w$. Note that all vertices now have degree at most 3. The construction works basically since the vertices $v_0,v_2,\ldots,v_{2d}$ all get the same color — I'll let you work out the details.