On the closure of triangle-free graphs under substitution

DOI10.1016/0020-0190(90)90143-LzbMath0702.68056OpenAlexW2075046674MaRDI QIDQ915449

Stephan Olariu

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90143-l

zbMATH Keywords

perfect graphsclosurepolynomial-time algorithmssubstitution

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items

On semi-\(P_ 4\)-sparse graphs ⋮ All minimal prime extensions of hereditary classes of graphs ⋮ On the closure of graphs under substitution ⋮ Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ A finiteness theorem for primal extensions ⋮ On minimal prime extensions of a four-vertex graph in a prime graph ⋮ Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time ⋮ Independent sets in \((P_4+P_4\),triangle)-free graphs ⋮ Extension of hereditary classes with substitutions

Cites Work

• Unnamed Item
• Topics on perfect graphs
• Bull-free Berge graphs are perfect
• Normal hypergraphs and the perfect graph conjecture
• Incremental modular decomposition