On graphs without \(P_ 5\) and \(\overline {P}_ 5\) (Q1903716): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Jean-Luc Fouquet / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Frédéric Maire / rank | |||
Normal rank |
Revision as of 08:01, 11 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On graphs without \(P_ 5\) and \(\overline {P}_ 5\) |
scientific article |
Statements
On graphs without \(P_ 5\) and \(\overline {P}_ 5\) (English)
0 references
13 May 1996
0 references
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.
0 references
chromatic number
0 references
coloring
0 references