Prof. Dr.
Stefan
Hougardy
This page
contains updates for my paper Classes
of Perfect Graphs, Discrete Mathematics 306 (2006),
2529-2571
April 22, 2009
As pointed out by Prof. Ait Haddadene the table on page 2537
(page 13 in the preprint) contains an omission: Tucker showed that
there exists an O(n3) combinatorial algorithm to color K4-free
Berge graphs. This can be found in the paper: Alan Tucker: A Reduction Procedure for Coloring Perfect
K4-Free Graphs, Journal of
Combinatorial Theory, Series B 43, 151-172 (1987).