Chromatic Equals Clique

A graph is chordal exactly when it has a perfect elimination ordering; maximum cardinality search finds one in $O(n+m)$; and greedy coloring in reverse elimination order proves $\chi(G) = \omega(G) + 1$, so coloring is NP-hard while maximum clique and maximum independent set stay polynomial.

A graph is chordal exactly when it has a perfect elimination ordering; maximum cardinality search finds one in $O(n+m)$; and greedy coloring in reverse elimination order proves $\chi(G) = \omega(G)$, so coloring, maximum clique and maximum independent set are all polynomial.

A graph is chordal exactly when it has no induced cycle of length exactly $3$; maximum cardinality search finds a perfect elimination ordering in $O(n+m)$; and greedy coloring in reverse elimination order proves $\chi(G) = \omega(G)$, so coloring, maximum clique and maximum independent set are all polynomial.

A graph is chordal exactly when it has a perfect elimination ordering; maximum cardinality search finds one in $O(m \log n)$ with a priority queue; and greedy coloring in reverse elimination order proves $\chi(G) \le \omega(G)\log n$, so coloring, maximum clique and maximum independent set are all polynomial.