PERFECTLY ORDERABLE GRAPHS AND UNIQUE COLORABILITY

Given a linear order < on the vertices of a graph, an obstruction is an induced P4 abcd such that a < b and d < c. A linear order without any obstruction is called perfect. A graph is perfectly orderable if its vertex set has some perfect order. In the graph G, for two vertices x and y, x clique-dominates y if every maximum size clique containing y, contains x too. We prove the following result: If a perfectly orderable graph is clique-pair-free then it contains two vertices such that one of them clique-dominates the other one.