An algorithm for finding homogeneous pairs
\((Q_1,Q_2)\) is a homogeneous pair in an undirected finite graph \(G= (V,E)\) if \(Q_i\subset V\) for \(i\in \{1,2\}\), \(|Q_1 |\geq 2\) or \(|Q_2 |\geq 2\), \(|V \backslash (Q_1\cup Q_2) |\geq 2\) and every vertex \(v\in V\backslash (Q_1\cup Q_2)\) is adjacent to either all or none of the vertices of \(Q_i\), \(i\in \{1,2\}\). Homogeneous pairs are of interest in connection with the strong perfect graph conjecture---it is known that minimally imperfect graphs contain no homogeneous pair. This paper describes an \(O(mn^3)\) time bounded algorithm for determining whether a given graph contains a homogeneous pair, and, if possible, for finding one. Hereby \(n=|V|\) and \(m=|E|\).
- Algorithms for some H-join decompositions
- Algorithms for the homogeneous set sandwich problem
- An efficient algorithm for solving the homogeneous set sandwich problem
- The pair completion algorithm for the homogeneous set sandwich problem
- An efficient algorithm for finding a two-pair, and its applications
- \(P_ 4\)-trees and substitution decomposition
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Bull-free Berge graphs are perfect
- Comparability graphs and a new matroid
- Depth-First Search and Linear Graph Algorithms
- scientific article; zbMATH DE number 3882470 (Why is no real title available?)
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3896983 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Incremental modular decomposition
- Normal hypergraphs and the perfect graph conjecture
- Computing pairings using x-coordinates only
- The sandwich problem for decompositions and almost monotone properties
- An efficient algorithm for finding a two-pair, and its applications
- Algorithms for some H-join decompositions
- Counting List Matrix Partitions of Graphs
- Computing \(H\)-joins with application to 2-modular decomposition
- Coloring perfect graphs with no balanced skew-partitions
- Claw-free graphs, skeletal graphs, and a stronger conjecture on , , and
- A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants)
- Graph parameters measuring neighbourhoods in graphs-bounds and applications
This page was built for publication: An algorithm for finding homogeneous pairs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q674438)
