On the \(P_ 4\)-structure of perfect graphs. V: Overlap graphs
type: Item
instance of: scholarly article
title: On the \(P_ 4\)-structure of perfect graphs. V: Overlap graphs
zbMATH Open document ID: 0871.05019
author: Chính T. Hoàng
author: Stefan Hougardy
author: Frédéric Maffray
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-09-24T00:00:00Z
review text: An odd hole in a graph is an induced cycle with length odd and at least 5. A Berge graph is a graph with no odd hole or its complement. The \(k\)-overlap graph of a graph \(G\) has a vertex for each induced \(P_4\) in \(G\), and two vertices are adjacent if the corresponding \(P_4\)'s have exactly \(k\) vertices of \(G\) in common. Here \(P_4\) denotes the path with 4 vertices. It is shown that for \(k=2,3\), if the \(k\)-overlap graph of a Berge graph is triangle-free then \(G\) is perfect. This yields that if the 3-overlap graph of \(G\) is bipartite then \(G\) is perfect, and if \(G\) is \(C_5\)-free and the 2-overlap graph of \(G\) is bipartite then \(G\) is perfect. Similarly, if \(G\) is \(C_5\)-free and the 1-overlap graph is bipartite then \(G\) is perfect. The result for \(k=3\) extends some recent work on `partner graphs'.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 934812
zbMATH Keywords: perfect graphs
zbMATH Keywords: overlap graphs
zbMATH Keywords: odd hole
zbMATH Keywords: cycle
zbMATH Keywords: Berge graph
zbMATH Keywords: path
reviewed by: Colin McDiarmid
MaRDI profile type: Publication
full work available at URL: jctb.1996.0042
OpenAlex ID: W2057237215
DOI: 10.1006/JCTB.1996.0042
description: scientific article; zbMATH DE number 934812