# Graph Families that are easy to color

What are the non-trivial graph families that have a known chromatic number, or an easy way (polynomial-time algorithm) to compute the latter.

Examples would be:

• Kneser graphs
• Chordal graphs

Do you know any other families?

Motivation:

We are looking for interesting classes on which we can test a proper coloring heuristic. This is why we wanted some graphs that are not so easy to color but in the same time have a known chromatic number so we can evaluate the quality of the heuristic.

• As evidenced by Juho's answer, this question is rather broad. Why are you asking? What do you need such classes for?
– Raphael
Jun 30, 2015 at 13:03
• I suggest adding that context/motivation to the question. I think it helps focus the question and improve the likelihood you'll get useful answers. You can edit your question to include that information in it.
– D.W.
Jul 1, 2015 at 7:23
• It's straightforward to model $k$-coloring as SAT/CSP too, so maybe solvability in polynomial time doesn't matter too much. The solvers should handle many cases easily.
– Juho
Jul 1, 2015 at 9:34
• @IssamT. Easy-to-colour graphs might not be a good test for your heuristic. In a sense, they're very special and not typical of general graphs. For example, what if your heuristic works well on easy-to-colour graphs (where you don't really need a heuristic to help you) but terribly on general graphs (where a heuristic would be really useful)? You'd then conclude that your heuristic is great when actually, it doesn't help at all. Jul 1, 2015 at 9:43
• @IssamT. Well, why not just compute the exact value of the chromatic number for the graphs as well? I guess it's fine even if it took minutes to compute it (but again, SAT/CSP solvers tend to be good here).
– Juho
Jul 1, 2015 at 13:23