Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets

DOI10.1016/0012-365X(92)90623-NMaRDI QIDQ1197003zbMATH OpenOpenAlexFDO

Authors S. Singh

Publication date 16 January 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(92)90623-n

zbMATH Keywords

chromatic numberclique sizeincidence matrixlinear perfect matricesstar cutsetsstrong perfect graph conjecture

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Association schemes, strongly regular graphs (05E30)

Review text

[For Part II see ibid. 110, No. 1-3, 81-118 (1992; Zbl 0774.05064).] A graph \(G\) is perfect if for every vertex-induced subgraph \(H\) of \(G\), the largest clique size of \(H\) equals the chromatic number of \(H\). Berge has conjectured---the Strong Perfect Graph Conjecture---that a graph is perfect if and only if the graph and its complement contain no odd-length chordless circuits other than triangles. A (0,1) matrix is linear if it does not contain a 2-by-2 submatrix of all ones. This paper studies graphs whose vertex-clique incidence matrix is linear. Such graphs are characterized by the property that they contain no induced subgraph isomorphic to \(K_ 4-e\), a complete graph on 4 vertices with on edge removed. This paper presents a new matrix-based proof of the Strong Perfect Graph Conjecture for \((K_ 4-e)\)-free graphs.

Recommendations

• Publication:4731202
• Progress on perfect graphs
• Perfect graphs with no \(P_ 5\) and no \(K_ 5\)
• On the strong perfect graph conjecture
• The strong perfect graph theorem

Cites work

• An algorithm for finding clique cut-sets
• Compositions for perfect graphs
• scientific article; zbMATH DE number 3887730 (Why is no real title available?)
• scientific article; zbMATH DE number 3889583 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3608050 (Why is no real title available?)
• scientific article; zbMATH DE number 3420800 (Why is no real title available?)
• Normal hypergraphs and the perfect graph conjecture
• Odd cycles and matrices with integrality properties
• On a Class of Totally Unimodular Matrices
• On certain polytopes associated with graphs
• Perfect zero–one matrices
• Properties of balanced and perfect matrices
• Recognizing claw-free perfect graphs
• Star-cutsets and perfect graphs
• Structural properties and decomposition of linear balanced matrices
• Structural properties and recognition of restricted and strongly unimodular matrices
• Testing balancedness and perfection of linear matrices
• The Strong Perfect Graph Conjecture for Planar Graphs
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• Topics on perfect graphs

Cited in

(11)

• Articulation sets in linear perfect matrices. II: The wheel theorem and clique articulations
• Near-perfect matrices
• Square-free perfect graphs.
• Odd cycles and matrices with integrality properties
• Almost perfect matrices and graphs.
• Perfect k‐line graphs and k‐total graphs
• scientific article; zbMATH DE number 4116566 (Why is no real title available?)
• scientific article; zbMATH DE number 867633 (Why is no real title available?)
• A mickey-mouse decomposition theorem
• Addendum to: M. Conforti and M. R. Rao, ``Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets, Discrete Mathematics 104 (1992) 23--47
• Testing balancedness and perfection of linear matrices

This page was built for publication: Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1197003)