## Basics of Perfect Graphs

A perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph.

• Prove that bipartite graphs are perfect. Prove that the line graphs of bipartite graphs are perfect.

• A graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. Prove that chordal graphs are perfect.

• An interval graph is the intersection graph of a multiset of intervals on the real line. Prove that interval graphs are chordal graphs and hence perfect.

• Comparability graphs are formed from partially ordered sets by connecting pairs of elements by an edge whenever they are related in the partial order. Prove that comparability graphs are perfect.

• $G$ has a clique $K$ such that $G − K$ has two components whose vertex sets are $A$, $B$. The subgraphs induced by $A \cup K$ and by $B \cup K$ are both perfect. Prove that $G$ is perfect.

Source: folklore
delete retag edit Add to a Problem Set