The strong perfect graph conjecture holds for diamonded odd cycle-free graphs
adjacency matrixbipartite graphdiamonded odd cycleincidence matrixperfect matricesstar cut setstrong perfect graph conjecture
Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75)
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.
- Balanced matrices
- Coloring perfect \((K_ 4\)-e)-free graphs
- scientific article; zbMATH DE number 3887724 (Why is no real title available?)
- scientific article; zbMATH DE number 3598234 (Why is no real title available?)
- scientific article; zbMATH DE number 3322855 (Why is no real title available?)
- Properties of balanced and perfect matrices
- Star-cutsets and perfect graphs
- Structural properties and decomposition of linear balanced matrices
- Structure theorems for some circular-arc graphs
- The Strong Perfect Graph Conjecture for Planar Graphs
- The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
- The validity of the strong perfect-graph conjecture for (K₄-e)-free graphs
- Building counterexamples
- Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs
- Odd cycles and matrices with integrality properties
- Classes of perfect graphs
- Families of graphs complete for the strong perfect graph Conjecture
- scientific article; zbMATH DE number 1009511 (Why is no real title available?)
- scientific article; zbMATH DE number 2192137 (Why is no real title available?)
- Strong cliques in diamond-free graphs
- A proof of Hougardy's conjecture for diamond-free graphs
This page was built for publication: The strong perfect graph conjecture holds for diamonded odd cycle-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1208345)
