The strong perfect graph conjecture holds for diamonded odd cycle-free graphs
type: Item
instance of: scholarly article
title: The strong perfect graph conjecture holds for diamonded odd cycle-free graphs
zbMATH Open document ID: 0778.05069
DOI: 10.1016/0012-365X(92)90697-E
author: Olivia M. Carducci
published in: Discrete Mathematics
publication date: 1993-05-16T00:00:00Z
review text: Let \(G_ 5=P_ 4\lor K_ 1\) and \(J_ 5=C_ 4\lor K_ 1\). The authoress defines an odd cycle \(C\) of a (simple) graph \(G\) to be a diamonded odd cycle if \(C\) induces \(G_ 5\) or \(J_ 5\) or if \(C\) has length more than five and two chords \(xy,xz\) with \(yz\) an edge of \(C\) and there is a vertex \(w\) not on \(C\), adjacent to \(y\) and \(z\) but not \(x\) and there is no edge of \(C\) (other than \(yz)\) which lies on a triangle induced by the vertices of \(C\). She then proves that the strong perfect graph conjecture is true for graphs which do not contain a diamonded odd cycle. The main technique of proof is to go from the graph \(G\) to its clique- vertex incidence matrix \(M\) and then to the bipartite graph \(H\) for which \(M\) is the adjacency matrix between the vertices of the two parts \(S\) and \(T\) of the vertex set of \(H\). The vertices in \(S\) and \(T\) correspond to the cliques and vertices of \(G\). Assuming \(G\) to be a minimal imperfect graph without diamonded odd cycles, it is first shown that to verify SPGC (for such graphs) it is enough to show that \(G\) has no odd hole of size five or more. Assuming the contrary, it is eventually proved that \(G\) contains a star cut set, and a theorem of V. Chvátal provides the necessary contradiction. Several new definitions are introduced to effect the translation of the conditions from \(G\) to \(H\) and the recent results of Conforti and Rao on balanced and perfect matrices are extensively used. A clear presentation is achieved by breaking up the steps into several lemmas. Even with this, a monstrous lemma (Lemma 6) leads to several cases, only one of which is presented in full detail. For the others, the authoress's Ph. D. thesis is cited.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05B20
zbMATH DE Number: 166350
zbMATH Keywords: strong perfect graph conjecture
zbMATH Keywords: diamonded odd cycle
zbMATH Keywords: incidence matrix
zbMATH Keywords: bipartite graph
zbMATH Keywords: adjacency matrix
zbMATH Keywords: star cut set
zbMATH Keywords: perfect matrices
Wikidata QID: Q122924544
MaRDI profile type: Publication
cites work: Q5603089
cites work: Balanced matrices
cites work: Star-cutsets and perfect graphs
cites work: Q4165164
cites work: Structural properties and decomposition of linear balanced matrices
cites work: Properties of balanced and perfect matrices
cites work: Q3222219
cites work: The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
cites work: The validity of the strong perfect-graph conjecture for \((K_4-e)\)-free graphs
cites work: The Strong Perfect Graph Conjecture for Planar Graphs
cites work: Structure theorems for some circular-arc graphs
cites work: Coloring perfect \((K_ 4\)-e)-free graphs
description: scientific article; zbMATH DE number 166350