patternMinor
Graph Families that are easy to color
Viewed 0 times
grapharecolorfamilieseasythat
Problem
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:
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.
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.
Solution
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.
To shortly summarize the above, one could highlight perfect graphs (a superclass of chordal graphs), and graphs of bounded treewidth.
Context
StackExchange Computer Science Q#44056, answer score: 8
Revisions (0)
No revisions yet.