Print LaTeX

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 flag offensive retag edit Add to a Problem Set

Related books