HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

On the complexity of recognizing decomposable perfect graphs

Abstract : Chvátal, Lenhart and Sbihi identified six classes of graphs that are perfect if and only if two subgraphs induced by a specific colouring of the vertices are perfect. It is well-known that one of these classes is recognizable in polynomial time. We prove that the recognition of the five other classes is NP-complete.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00099295
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 8:52:33 AM
Last modification on : Thursday, February 3, 2022 - 11:10:30 AM

Identifiers

  • HAL Id : inria-00099295, version 1

Citation

Cristina Bazgan, Laurent Juban. On the complexity of recognizing decomposable perfect graphs. [Intern report] A00-R-084 || bazgan00a, 2000, 13 p. ⟨inria-00099295⟩

Share

Metrics

Record views

147