# Finding a class of graphs for which vertex coloring is NP-hard

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.

• 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?" Feb 3 '17 at 23:25
• @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. Feb 3 '17 at 23:45
• 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. Feb 4 '17 at 0:25
• @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. Feb 4 '17 at 2:39
• 3-coloring is NP-hard on planar graphs with maximum degree at most 4. ​ ​
– user12859
Feb 4 '17 at 5:48