scientific article; zbMATH DE number 4116566

From MaRDI portal
Publication:4731202





[For the entire collection see Zbl 0676.00023.] This paper examines the structure of linear hypergraphs, hypergraphs in which two edges have at most one vertex in common, to develop a new proof of the Strong perfect graph conjecture for \((K_ 4-e)\)-free graphs (a \(K_ 4-e\) is formed by two triangles with an edge in common). The hypergraphs considered have as their edges the cliques of given graph. (Note that the clique hypergraph of \(K_ 4-e\) ist not linear). The analysis involves the examination of odd-length cycles in these clique hypergraphs. The strong perfect graph conjecture says that if neither graph G and its complement \(G^ c\) contain any odd-length \((>4)\) chordless circuit, then in any vertex-induced subgraph H of G (including G itself), the size of the largest clique in H equals the chromatic number of H.











This page was built for publication:

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