Search tip: add tags and a query to focus your search

By
kintali
on
Nov. 15, 2012
| Updated
on
May 19, 2013

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.

[debug] activity: 173.0