0
$\begingroup$

We know that for general graphs vertex coloring problem/ minimum clique cover problem are NP-hard and for perfect graphs, they can be solved in polynomial time. There are classes of graphs which are perfect, e.g., bipartite graphs, chordal graphs, linear graphs, etc.

My question is that:

Are there any families of graphs that we know for them vertex coloring problem/ minimum clique cover problem are NP-hard? I appreciate if someone can give the name of some of them or any reference for them (in case they exist).

I have a problem and I want to show that it is hard and I want to find such a family of graphs and use them as an instance for my problem.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I think you need to add some specifications to your problem. First, the term "hard" only makes sense with respect to a certain complexity class. I assume you mean NP-hard. Second, a family of graphs is very broad. What's preventing me from answering "the family that contains every graph?" $\endgroup$
    – Riley
    Commented Feb 3, 2017 at 23:25
  • $\begingroup$ @Riley Yes, I meant NP-hard. There are classes of graphs which are perfect, e.g., bipartite graphs, chordal graphs, linear graphs. I want to know whether there are such classes for them the mentioned problem are NP-hard? I think the family of all graphs is not correct because perfect graphs are subsets of them and those problems for perfect graphs are not NP-hard. As I said I specifically want to use to for a reduction to show NP-hardness of a problem. So, I need the instances of that class to be NP-hard for sure. $\endgroup$
    – m0_as
    Commented Feb 3, 2017 at 23:45
  • $\begingroup$ I'm sorry for my misconception of the problem. I should've taken more time to realize you were looking for a counterexample to prove its NP-hardness. I changed my incorrect answer. $\endgroup$
    – Riley
    Commented Feb 4, 2017 at 0:25
  • 1
    $\begingroup$ @m0_as I'm confused about your explanation as to why the family of all graphs is an incorrect answer. Obviously it's not helpful for your purpose, but the vertex coloring problem is still NP-hard on that family, as you asked. You say it's invalid because for some instances it isn't NP-hard, but it doesn't make sense to say that a problem is NP-hard for a specific case. You even asked a question previously, and the answer explains this very well. $\endgroup$
    – Riley
    Commented Feb 4, 2017 at 2:39
  • 1
    $\begingroup$ 3-coloring is NP-hard on planar graphs with maximum degree at most 4. ​ ​ $\endgroup$
    – user12859
    Commented Feb 4, 2017 at 5:48

1 Answer 1

Reset to default
1
$\begingroup$

This PDF defines a graph for which solving a 3-SAT formula is equivalent to determining if the graph is 3-colorable. Finding the vertex coloring of these graphs would solve the 3-SAT problem, so the vertex coloring problem on these graphs is at least as hard as an NP-complete problem. Therefore, solving the vertex coloring problem on these graphs is NP-hard.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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