Suggest a Book

# Basics of Perfect Graphs

[debug] activity: 136.0

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.

Level:
Source: folklore
delete retag edit Add to a Problem Set

Shiva Kintali
941 2 8 34
http://www.cs.princeton.e...
POST AN EXERCISE POST A VIDEO POST NOTES POST MULTIPLE-CHOICE QUESTION

## Stats

Posted: Nov 15 '12

Seen: 134 times

Last updated: yesterday