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!

  • $\begingroup$ 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. $\endgroup$ – David Richerby Mar 10 '16 at 16:38
  • $\begingroup$ Thank you for this, there is something in the notation of reductions that always gets me confused! $\endgroup$ – Sara Mar 10 '16 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.

  • $\begingroup$ This has cleared things up for me quiet a lot, thank you very much! $\endgroup$ – Sara Mar 10 '16 at 17:27

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.