On graphs without \(P_ 5\) and \(\overline {P}_ 5\) (Q1903716): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 15:01, 1 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