On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
type: Item
instance of: scholarly article
title: On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
zbMATH Open document ID: 0837.05095
DOI: 10.1016/0012-365X(94)00155-X
author: Vassilis Giakoumakis
author: Henri Thuillier
author: Jean-Luc Fouquet
author: Frédéric Maire
published in: Discrete Mathematics
publication date: 1996-05-13T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 825340
zbMATH Keywords: chromatic number
zbMATH Keywords: coloring
MaRDI profile type: Publication
cites work: Graphs with no induced \(C_ 4\) and \(2K_ 2\)
cites work: Q3899969
cites work: Q4193514
cites work: A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
cites work: Incidence matrices and interval graphs
cites work: Q5749319
cites work: On brittle graphs
cites work: A new property of critical imperfect graphs and some consequences
cites work: Prime Testing for the Split Decomposition of a Graph
full work available at URL: 0012-365x(94)00155-x
OpenAlex ID: W1529247354
description: scientific article; zbMATH DE number 825340