Neighborhood perfect graphs (Q1081622)

Let G be a graph. The authors denote by \(\alpha_ N(G)\) the maximum number of edges of G such that no two of them belong to the same neighborhood subgraph of G (that is a subgraph induced by a vertex v and the vertices adjacent to v). They denote by \(\rho_ N(G)\) the minimum number of vertices whose neighborhood subgraphs cover the edge set of G. A graph G is called neighborhood perfect if \(\rho_ N(G')=\alpha_ N(G')\) holds for every induced subgraph G' of G. Such a graph contains neither induced cycles of odd length at least five nor complements of such cycles. In view of Berge's strong perfect graph conjecture, \textit{C. Berge} [Automata Theory, Internat. School Phys. Ravello 1964, 25-34 (1966; Zbl 0187.213)], it is expected that such a graph is perfect in the sense of Berge. The main theorem of the paper characterizes those chordal graphs which are neighborhood perfect by excluding a family of induced subgraphs. It follows from the proof that the parameter \(\rho_ N(G)\) \((=\alpha_ N(G))\) can be computed in polynomial time. The authors give a linear algorithm to compute it for the particular case of interval graphs.