Recognition
Interval iff chordal + co-comparability. Recognition in O(V+E) via PQ-trees or lexicographic BFS.
Advertisement
Coloring
Sort by left endpoint. Greedy: assign smallest available color. Optimal. O(V log V).
Advertisement
Max clique / max independent set
Both polynomial. Clique = max intervals stabbed by a point. Indep = max non-overlapping via greedy.
Scheduling applications
Meeting room allocation. Task scheduling with deadlines. Any 'time interval conflict' problem.