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.
Posted: Nov 15 '12
Seen: 98 times
Last updated: 2 days ago
