On graphs without \(P_ 5\) and \(\overline {P}_ 5\) (Q1903716): Difference between revisions

The class of graphs without \(P_5\) and \(\overline {P_5}\) contains the class of cographs considered by \textit{G. D. Corneil} et al. [Discrete Appl. Math. 3, 163-174 (1981; Zbl 0463.05057)] and the class of graphs without \(C_4\) and \(2K_2\) characterized by \textit{Z. Blázsik} et al. [Discrete Math. 115, No. 1-3, 51-55 (1993; Zbl 0772.05082)]. The authors investigate the structure of graphs without \(P_5\) and \(\overline {P_5}\), enlighten the positions of \(C_5 s\) in such graphs, and give a \(\chi\)-binding function bounding the chromatic number \(\chi (G)\) by \(\omega (G) \cdot (\omega (G) + 1)/2\) for graphs \(G\) in this class. Additionally an \(O(n^4)\) algorithm is given for coloring the vertices of a graph \(G\) without \(P_5\) and \(\overline {P_5}\) with at most \(O (\omega (G)^2)\) colors.