NP-hardness of the recognition of coordinated graphs
DOI10.1007/S10479-008-0392-4zbMATH Open1279.05069OpenAlexW2073583324MaRDI QIDQ839773FDOQ839773
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) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- Über iterierte Clique-Graphen
- The strong perfect graph theorem
- Recognizing Berge graphs
- Algorithmic aspects of clique-transversal and clique-independent sets
- Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
- Partial characterizations of coordinated graphs: Line graphs and complements of forests
- Characterization and recognition of Helly circular-arc clique-perfect graphs
- Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
Cited In (5)
- Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
- Partial characterizations of coordinated graphs: Line graphs and complements of forests
- Distinguishing graphs via cycles
- Recognizing tough graphs is NP-hard
- 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q839773)
