A Transformation Which Preserves the Clique Number

AbstractWe 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