On \(P_4\)-transversals of perfect graphs (Q1567276): Difference between revisions

A \(P_{4}\)-transversal of a graph \(G\) is a subset \(T\) of its vertex set meeting every \(P_{4}\) of \(G\). If in addition, \(T\) induces a \(P_{4}\)-free subgraph, it is a two-sided \(P_{4}\)-transversal. The authors conjecture that Berge graphs with a two-sided \(P_{4}\)-transversal are perfect. A graph is \(P_{4}\)-stable if it has a \(P_{4}\)-transversal inducing a stable set. It is strongly \(P_{4}\)-stable if it has a stable \(P_{4}\)-transversal meeting every \(P_{4}\) in an end point or every \(P_{4}\) in a midpoint. The authors prove the following: (1) \(P_{4}\)-stable graphs without odd holes are perfect. (2) Recognizing \(P_{4}\)-stable graphs is NP-complete. (3) Strongly \(P_{4}\)-stable graphs are perfectly ordereable (and hence strongly perfect and perfect). (4) Strongly \(P_{4}\)-stable graphs can be recognized in polynomial time. (5) A Berge graph \(G\) with a \(P_{4}\)-transversal \(T\) inducing a threshold graph and meeting every \(P_{4}\) in an end point or every \(P_{4}\) in a midpoint is perfect. They discuss in detail how their results enhance the class of known perfect graphs.