The strong perfect graph conjecture for pan-free graphs
type: Item
instance of: scholarly article
title: The strong perfect graph conjecture for pan-free graphs
zbMATH Open document ID: 0661.05057
DOI: 10.1016/0095-8956(89)90019-1
author: Stephan Olariu
published in: Journal of Combinatorial Theory. Series B
publication date: 1989-01-01T00:00:00Z
full work available at URL: https://digitalcommons.odu.edu/cgi/viewcontent.cgi
review text: A graph \(G\) is perfect if for every induced subgraph \(F\) of \(G\), the chromatic number \(\chi(F)\) equals the largest number \(\omega(F)\) of pairwise adjacent vertices in \(F\). Berge's famous Strong perfect graph conjecture asserts that a graph \(G\) is perfect if and only if neither \(G\) nor its complement \(\overline{G}\) contains an odd chordless cycle of length at least five. Its resolution has eluded researchers for more than twenty years. We prove that the conjecture is true for a class of graphs which strictly contains the claw-free graphs.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C17
zbMATH DE Number: 4079480
zbMATH Keywords: clique number
zbMATH Keywords: chromatic number
zbMATH Keywords: Strong perfect graph conjecture
zbMATH Keywords: claw-free graphs
MaRDI profile type: Publication
OpenAlex ID: W2047069830
cites work: Star-cutsets and perfect graphs
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: Q5596090
cites work: The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
cites work: Critical perfect graphs and perfect 3-chromatic graphs
description: scientific article; zbMATH DE number 4079480