Beyond Perfection: Computational Results for Superclasses

Arnaud Pêcher () and Annegret K. Wagler ()
Additional contact information
Arnaud Pêcher: Université de Bordeaux, Laboratoire Bordelais de Recherche Informatique (LaBRI)/INRIA Sud-Ouest
Annegret K. Wagler: Université Blaise Pascal (Clermont-Ferrand II), Laboratoire d’Informatique, de Modélisation et d’Optimisation des Systèmes (LIMOS)/CNRS

A chapter in Facets of Combinatorial Optimization, 2013, pp 133-161 from Springer

Abstract: Abstract We arrived at the Zuse Institute Berlin, Annegret as doctoral student in 1995 and Arnaud as postdoc in 2001, both being already fascinated from the graph theoretical properties of perfect graphs. Through encouraging discussions with Martin, we learned about the manifold links of perfect graphs to other mathematical disciplines and the resulting algorithmic properties based on the theta number (where Martin got famous for, together with Laci Lovász and Lex Schrijver). This made us wonder whether perfect graphs are indeed completely unique and exceptional, or whether some of the properties and concepts can be generalized to larger graph classes, with similar algorithmic consequences—the starting point of a fruitful collaboration. Here, we answer this question affirmatively and report on the recently achieved results for some superclasses of perfect graphs, all relying on the polynomial time computability of the theta number. Finally, we give some reasons that the theta number plays a unique role in this context.

Keywords: Theta Function; Chromatic Number; Graph Class; Perfect Graph; Clique Number (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-38189-8_6

Ordering information: This item can be ordered from
http://www.springer.com/9783642381898

DOI: 10.1007/978-3-642-38189-8_6

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().