Meyniel weakly triangulated graphs. I: Co-perfect orderability (Q678852)

An algorithm is given that finds for any \(P_5\)-free weakly triangulated graph a perfect order in polynomial time. This proves a well-known conjecture of Chvátal that every \(P_5\)-free weakly triangulated graph is perfectly orderable. A graph is weakly triangulated if neither itself nor its complement contain a chordless cycle of length five or more. A graph is pefectly orderable if it has a perfect order, i.e. a linear order of the vertices such that for each induced ordered subgraph the number of colors used by the following greedy algorithm equals the chromatic number of the subgraph. The greedy algorithm is: given a linear order of the vertices of a graph, color the vertices in order, assigning to each the smallest positive integer (each integer representing a color) not assigned to any adjacent vertex already colored.