Exercises

1. 

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

(ii) Prove that the following properties hold:

abΓabbaΓbaabΓ*abbaΓ*ba

si224_e

2. The complete graph K2 has two implication classes. Give a formula for | I(Kn) |si225_e 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?

f05-16-9780444515308

Figure 5.16

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.