www.wikidata.de-de.nina.az

Schwacher Perfekte Graphen Satz Der schwache Perfekte Graphen Satz oder auch nur Perfekte Graphen Satz und Satz von Lová

Schwacher Perfekte-Graphen-Satz

Der schwache Perfekte-Graphen-Satz (oder auch nur Perfekte-Graphen-Satz und Satz von Lovász) ist ein mathematischer Satz aus der Graphentheorie, der sich mit Strukturen, die bei Eckenfärbungen auftreten, beschäftigt. Er wurde 1972 erstmals von László Lovász bewiesen.

„Ein Graph G ist genau dann perfekt, wenn sein komplementärer Graph Gc perfekt ist.“

Im Folgenden bezeichne für einen Graphen G seine Eckenmenge, einen von induzierter Teilgraphen, die chromatische Zahl, die Cliquenzahl, die Stabilitätszahl und die Zusammenhangszahl.

Die folgenden Bedingungen sind dann (formal) äquivalent:

  1. für alle (G perfekt).
  2. für alle (Gc perfekt).
  3. für alle .

Literatur Bearbeiten

  • Reinhard Diestel: Graphentheorie. Springer 2006, ISBN 3-540-21391-0, Satz 4.5.4

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der schwache Perfekte Graphen Satz oder auch nur Perfekte Graphen Satz und Satz von Lovasz ist ein mathematischer Satz aus der Graphentheorie der sich mit Strukturen die bei Eckenfarbungen auftreten beschaftigt Er wurde 1972 erstmals von Laszlo Lovasz bewiesen Ein Graph G ist genau dann perfekt wenn sein komplementarer Graph Gc perfekt ist Im Folgenden bezeichne fur einen Graphen G V displaystyle V seine Eckenmenge G A displaystyle G A einen von A V displaystyle A subset V induzierter Teilgraphen x G displaystyle chi G die chromatische Zahl w G displaystyle omega G die Cliquenzahl a G displaystyle alpha G die Stabilitatszahl und die k G displaystyle k G Zusammenhangszahl Die folgenden Bedingungen sind dann formal aquivalent x G A w G A displaystyle chi G A omega G A fur alle A V displaystyle A subseteq V G perfekt k G A a G A displaystyle k G A alpha G A fur alle A V displaystyle A subseteq V Gc perfekt a G A w G A A displaystyle alpha G A omega G A geq A fur alle A V displaystyle A subseteq V Literatur BearbeitenReinhard Diestel Graphentheorie Springer 2006 ISBN 3 540 21391 0 Satz 4 5 4Weblinks BearbeitenEric W Weisstein Perfect Graph Theorem In MathWorld englisch Abgerufen von https de wikipedia org w index php title Schwacher Perfekte Graphen Satz amp oldid 186686605