Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs (Q2178334)

A study on perfect graphs are one of the toughest areas akin to the study of graph minors. The authors have done an excellent piece of work on one class of graphs called \(P_4\) tidy and tree-cographs. A graph \(G\) with vertex set \(V\) and edge set \(E\) is said to be \(P_4\) tidy if for every vertex set \(W\) inducing a \(P_4\) in \(G\) there is at most one vertex \(u\in V\setminus W\) such that the graph induced by \(W\cup\{u\}\) contains at least two induced \(P_4\)'s. By a tree-cograph they mean the following: 1) Every tree is tree-cograph; 2) If a graph is a tree-cograph then so is its complement; 3) The disjoint union of tree graphs is again a tree-cograph. Their characterization for neighborhood perfect graph in terms of minimal forbidden induced subgraphs for both \(P_4\) tidy and tree-cograph classes are outstanding. They also succeeded in producing linear-time recognition algorithms for neighborhood-perfectness of \(P_4\)-tidy graphs and tree-cographs besides proving NP hardness result for the task of computing \(\alpha_n\) and \(\rho_n\) for any given \(P_4\)-tidy graph or tree-cograph, where \(\alpha_n\) and \(\rho_n\) stand for the size of maximum neighborhood-independent set and size of a minimum neighborhood-covering set. The authors also remarked honestly their inability to say categorically regarding \textit{B. Courcelle} et al.'s different approach in 2000 [Theory Comput. Syst. 33, No. 2, 125--150 (2000; Zbl 1009.68102)], for getting linear time algorithms for \(P_4\) tidy class of graphs that are expressible in a certain monadic second-order logic could go well with the definition of neighborhood-perfectness. To sum up, the author's work in the paper is exhaustive and novel and certainly could open new vistas for contemporary researchers in this area.