4
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ As evidenced by Juho's answer, this question is rather broad. Why are you asking? What do you need such classes for? $\endgroup$ – Raphael♦ Jun 30 '15 at 13:03
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W.♦ Jul 1 '15 at 7:23
  • 1
    $\begingroup$ 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. $\endgroup$ – Juho Jul 1 '15 at 9:34
  • 1
    $\begingroup$ @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. $\endgroup$ – David Richerby Jul 1 '15 at 9:43
  • 1
    $\begingroup$ @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). $\endgroup$ – Juho Jul 1 '15 at 13:23
7
$\begingroup$

Whenever you are interested in a (well-known) graph invariant, it's a good idea to check out ISGCI first. Have a look at graphs that have bounded chromatic number, or graphs for which computing the number is doable in polynomial time.

To shortly summarize the above, one could highlight perfect graphs (a superclass of chordal graphs), and graphs of bounded treewidth.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Gee, that's... comprehensive. $\endgroup$ – Raphael♦ Jun 30 '15 at 10:12

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.