A reduction procedure for coloring perfect \(K_ 4\)-free graphs (Q1096639): Difference between revisions

A \(K_ 3\)-contraction in a graph G consists in identifying the two non- adjacent vertices of a \(K_ 4-e\) subgraph of G. The title procedure consists in alternately applying this operation as long as possible and replacing the resulting graph G' by its set of leaves with respect to the neighbourhood N(x) of some vertex x of G' if x has been concerned by the first operation and G'-N(x) is not connected. The author shows that every \(K_ 4\)-free graph with no chordless odd-length circuit or complement of that (so every \(K_ 4\)-free perfect graph) is transformed into a \(((K_ 4-e)\)-free) graph \(G_ i\) of the same kind by this procedure and that G can be 3-coloured if and only if \(G_ i\) can. The constructive proof uses an 0(n 3) colouring algorithm. So the paper (when the announced paper ``Uniquely colorable perfect graphs. II'' of the author has appeared) presents an algorithmic proof of the validity of the strong perfect graph Conjecture for \(K_ 4\)-free graphs (which before was proved otherwise by the author [J. Comb. Theory, Ser. B 23, 143-149 (1977; Zbl 0376.05047)] and \textit{M. Burlet} [Étude algorithmique de certaines classes de graphes parfaits, Thèse de 3ème cycle, Univ. Grenoble (1981)].