NP-hardness of the recognition of coordinated graphs
DOI10.1007/s10479-008-0392-4zbMath1279.05069OpenAlexW2073583324MaRDI QIDQ839773
Gabriel Sueiro, Francisco J. Soulignac
Publication date: 3 September 2009
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10479-008-0392-4
computational complexityNP-complete problems\(\{\)gemC\(_{4}\), odd hole\(\}\)-free graphscoordinated graph recognition
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (4)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The strong perfect graph theorem
- Partial characterizations of coordinated graphs: Line graphs and complements of forests
- The ellipsoid method and its consequences in combinatorial optimization
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Algorithmic graph theory and perfect graphs
- Algorithmic aspects of clique-transversal and clique-independent sets
- Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
- Recognizing Berge graphs
- Über iterierte Clique-Graphen
- Characterization and recognition of Helly circular-arc clique-perfect graphs
- Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
This page was built for publication: NP-hardness of the recognition of coordinated graphs
