## Exercises

1.

(i) Prove that the forcing relation Γ* is an equivalence relation.

(ii) Prove that the following properties hold:

$\begin{array}{c}ab\text{Γ}{a}^{\prime }{b}^{\prime }⇔ba\text{Γ}{b}^{\prime }{a}^{\prime }\\ ab\text{Γ}*{a}^{\prime }{b}^{\prime }⇔ba\text{Γ}*{b}^{\prime }{a}^{\prime }\end{array}$

2. The complete graph K2 has two implication classes. Give a formula for $| I(Kn) |$ for n ≥ 2.

3. Which of the graphs in Figure 5.16 are comparability graphs? How many implication classes and color classes do they have?

4. Let G be a connected comparability graph whose complement $G¯$ is connected ...

Get Algorithmic Graph Theory and Perfect Graphs, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.