Algorithmic Graph Theory and Perfect Graphs, 2nd Edition

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 }\iff ba\text{Γ}{b}^{\prime }{a}^{\prime }\\ ab\text{Γ}*a^{\prime }{b}^{\prime }\iff ba\text{Γ}*b^{\prime }{a}^{\prime }\end{array}$

2. The complete graph K₂ has two implication classes. Give a formula for $\left|I\left(K_n\right)\right|$ 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?

Figure 5.16

4. Let G be a connected comparability graph whose complement $\overline{G}$ is connected ...