A Transformation Which Preserves the Clique Number

✍ Scribed by Michael U. Gerber; Alain Hertz

• Book ID: 102584451
• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 185 KB
• Volume: 83
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.2001.2061

✦ Synopsis

We introduce a graph transformation which preserves the clique number. When applied to graphs containing no odd hole and no cricket (a particular graph on 5 vertices) the transformation also preserves the chromatic number. Using this transformation we derive a polynomial algorithm for the computation of the clique number of all graphs in a class which strictly contains diamond-free graphs. Furthermore, the transformation leads to a proof that the Strong Perfect Graph Conjecture is true for two new classes of graphs and yields a polynomial time algorithm for the computation of the clique number and the chromatic number for both classes. One of these two classes strictly contains claw-free graphs.