scientific article; zbMATH DE number 4116566
[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.
- Coloring perfect \((K_ 4\)-e)-free graphs
- Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets
- Odd cycles and matrices with integrality properties
- Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
- Partial characterizations of circular-arc graphs
- Arboricity, \(h\)-index, and dynamic algorithms
- 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
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)