NP-hardness of the recognition of coordinated graphs

DOI10.1007/S10479-008-0392-4MaRDI QIDQ839773zbMATH OpenOpenAlexFDO

Authors Francisco J. Soulignac, Gabriel Sueiro

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

zbMATH Keywords

computational complexityNP-complete problems\(\{\)gemC\(_{4}\), odd hole\(\}\)-free graphscoordinated graph recognition

Mathematics Subject Classification ID

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)

Recommendations

• Exponential families of minimally non-coordinated graphs
• Partial characterizations of coordinated graphs: Line graphs and complements of forests
• Coordinated graphs and clique graphs of clique-Helly perfect graphs
• Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
• Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs

Cites work

• Algorithmic aspects of clique-transversal and clique-independent sets
• Algorithmic graph theory and perfect graphs
• Characterization and recognition of Helly circular-arc clique-perfect graphs
• Coordinated graphs and clique graphs of clique-Helly perfect graphs
• Exponential families of minimally non-coordinated graphs
• On clique-perfect and K-perfect graphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
• Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
• Partial characterizations of coordinated graphs: Line graphs and complements of forests
• Recognizing Berge graphs
• The ellipsoid method and its consequences in combinatorial optimization
• The strong perfect graph theorem
• Über iterierte Clique-Graphen

Cited in

(7)

• 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
• Coordinated graphs and clique graphs of clique-Helly perfect graphs
• Exponential families of minimally non-coordinated graphs
• 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)