1
$\begingroup$

Suppose we want to use a reduction of 3-colorability to a certain problem to prove said problem is NP-c. But to pull off the reduction, one needs to take a graph-class for which 3-coloring is NP-c and for a given input graph decompose its edges into as few independent groups as possible - basically edge-coloring the graph.

The function of this edge-decomposition is to allow replacing edges from each group by gadgets - gadgets from the same group would undesirably influence each other's function if they coincide. The issue is that the more groups there are, the higher complexity of the problem we reduce to (more gadget types) and thus less interesting result.

So, the question is: what classes of graphs can we allow as an input so that the task (vertex 3-coloring) remains NP-c, but also the maximum edge-chromatic number is minimized (and at most 6)?

Also, does the particular question change if we do not require the edge-coloring of the class to be P?

Clearly, one can take any graph and replace vertices od degrees 6 and higher by gadgets to reduce the max degree to 6 (maintaining equivalent problem). Vizing's theorem then guarantees the edge-chromatic number to be at most 7, in a constructive way. Is it possible to at least get to a vizing's class one while maintaining NP-c?

Any suggestions regarding where one might find some research tackling vertex-coloring hardness in respect to edge-coloring parameter?

$\endgroup$
  • 1
    $\begingroup$ "But to pull off the reduction, one needs to take a graph for which 3-coloring is NP-c and decompose its edges into as few independent groups as possible - basically edge-coloring the graph." Why is this approach necessary? Can you give an example to illustrate the problem? $\endgroup$ – Discrete lizard Apr 27 '17 at 13:44
  • $\begingroup$ I am of course looking for a class of graphs - that was my question. But since you point it out, I edited out the one time where I said "graph". $\endgroup$ – Nathan Whimeon Apr 28 '17 at 4:35

Your Answer

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

Browse other questions tagged or ask your own question.