Beyond perfection [Elektronische Ressource] : on relaxations and superclasses / von Annegret K. Wagler

Beyond Perfection:On Relaxations and SuperclassesH a b i l i t a t i o n s s c h r i f tzur Erlangung des akademischen Gradesdoctor rerum naturalium habilitatus (Dr. rer. nat. habil.)genehmigtdurch die Fakult¨at fu¨r Mathematikder Otto-von-Guericke-Universita¨t Magdeburgvon Dr. rer. nat. Annegret K. Waglergeb. am 04.12.1968 in LeipzigGutachter:Prof. Dr. Martin Gro¨tschelProf. Dr. Thomas LieblingProf. Dr. Robert WeismantelMagdeburg, den 10.01.2007iiZusammenfassungPerfekte Graphen, Anfang der 1960er Jahre von Claude Berge eingefu¨hrt,bilden eine Graphenklasse mit reichen strukturellen Eigenschaften. Charak-terisierungen perfekter Graphen bezu¨glich so verschiedener Konzepte wie• F¨arbungen von Graphen,• Additivit¨at der Graph-Entropie,• Ganzzahligkeit von Polytopen,verdeutlichen diese besonderen Eigenschaften und bilden gleichzeitig eineSchnittstelle zwischen den Gebieten Graphentheorie, Informationstheorie,Kombinatorischer Optimierung, Ganzzahliger Programmierung und Polye-dertheorie, siehe Sektion 1.1.Leider sind die meisten Graphen nicht perfekt und besitzen keine solcheherausragendenEigenschaften. Esistdaherinteressantzuerforschen,welcheGraphenzumindesthinsichtlich einiger Eigenschaften ‘fastperfekt’sindundwie man diese N¨ahe zu Perfektheit messen kann.