Enumerative aspects of certain subclasses of perfect graphs (Q1301836): Difference between revisions

The author considers the enumerative aspects of various graph classes such as \(P_4\)-free graphs, \((C_4, 2K_2, C_5)\)-free graphs, \((P_4, C_4)\)-free graphs, and \((P_4,C_4,2K_2)\)-free graphs. In particular, he determines the number of permutations \(\pi\) of \(1,2, \ldots, n\) such that the permutation graph defined by \(\pi\) is a \(P_4\)-free graph, respectively, a \((P_4,C_4,2K_2)\)-free graph. The author also considers the class of \((C_4,2K_2)\)-free graphs and gives a charaterization of these graphs (Theorem 4.1) which is already known in the literature; see, for example, \textit{Z. Blázsik} et al. [Graphs with no induced \(C_4\) and \(2K_2\), Discrete Math. 115, No.~1-3, 51-55 (1993; Zbl 0772.05082)] and \textit{F. Maffray} and \textit{M. Preissmann} [Linear recognition of pseudo-split graphs, Discrete Appl. Math. 52, No.~3, 307-312 (1994; Zbl 0805.05069)].