An algorithm for finding homogeneous pairs

DOI10.1016/0166-218X(95)00090-EzbMath0874.05052OpenAlexW1979621874MaRDI QIDQ674438

Hazel Everett, Sulamita Klein, Bruce A. Reed

Publication date: 9 November 1997

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

polynomial-time algorithmhomogeneous pair

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Counting List Matrix Partitions of Graphs ⋮ Computing \(H\)-joins with application to 2-modular decomposition ⋮ Coloring perfect graphs with no balanced skew-partitions ⋮ Graph parameters measuring neighbourhoods in graphs-bounds and applications ⋮ The sandwich problem for decompositions and almost monotone properties ⋮ Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bull-free Berge graphs are perfect
• \(P_ 4\)-trees and substitution decomposition
• Comparability graphs and a new matroid
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Normal hypergraphs and the perfect graph conjecture
• Incremental modular decomposition
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: An algorithm for finding homogeneous pairs