NP-hardness of the recognition of coordinated graphs
type: Item
instance of: scholarly article
title: NP-hardness of the recognition of coordinated graphs
zbMATH Open document ID: 1279.05069
author: Francisco J. Soulignac
author: Gabriel Sueiro
published in: Annals of Operations Research
publication date: 2009-09-03T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 5601633
zbMATH Keywords: computational complexity
zbMATH Keywords: coordinated graph recognition
zbMATH Keywords: \(\{\)gem
zbMATH Keywords: C\(_{4}\), odd hole\(\}\)-free graphs
zbMATH Keywords: NP-complete problems
MaRDI profile type: Publication
full work available at URL: s10479-008-0392-4
OpenAlex ID: W2073583324
cites work: Characterization and recognition of Helly circular-arc clique-perfect graphs
cites work: Q3428669
cites work: Partial characterizations of coordinated graphs: Line graphs and complements of forests
cites work: Q3595114
cites work: Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
cites work: Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
cites work: Recognizing Berge graphs
cites work: The strong perfect graph theorem
cites work: Über iterierte Clique-Graphen
cites work: Algorithmic graph theory and perfect graphs
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Algorithmic aspects of clique-transversal and clique-independent sets
cites work: On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
cites work: Q3645767
DOI: 10.1007/S10479-008-0392-4
description: scientific article; zbMATH DE number 5601633