Satz von Lovász

Satz von Lovász

Der schwache Perfekte-Graphen-Satz (oder auch nur Perfekte-Graphen-Satz ) 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 V seine Eckenmenge, GA einen von  A\subset V induzierter Teilgraphen, χ(G) die chromatische Zahl, ω(G) die Cliquenzahl, α(G) die Stabilitätszahl und die k(G) Zusammenhangszahl.

Die folgenden Bedingungen sind dann (formal) äquivalent:

  1. χ(GA) = ω(GA) für alle A \subseteq V (G perfekt).
  2. k(GA) = α(GA) für alle A \subseteq V (Gc perfekt).
  3. \alpha(G_A) \omega(G_A) \ge |A| für alle A \subseteq V.

Siehe auch: starker Perfekte-Graphen-Satz

Literatur

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Satz von Dilworth — Der Satz von Dilworth (nach Robert Palmer Dilworth) ist ein mathematischer Lehrsatz, welcher sowohl der Ordnungstheorie als auch der Diskreten Mathematik zuzuordnen ist. Er stellt einen Zusammenhang zwischen Ketten und Antiketten in einer… …   Deutsch Wikipedia

  • Lovász — ist der Familienname folgender Personen: Irén Lovász, ungarische Folk Sängerin László Lovász (* 1948), ungarischer Mathematiker Lázár Lovász (* 1942), ungarischer Hammerwerfer Zsuzsa Lovász (* 1976), ungarischer Handballspieler Lovász steht… …   Deutsch Wikipedia

  • Lovász-Local-Lemma — Das Lovász Local Lemma ist ein Hilfssatz aus der Wahrscheinlichkeitstheorie. Es verallgemeinert das Argument, dass die stochastische Unabhängigkeit von Ereignissen mit positiver Ausfallwahrscheinlichkeit eine positive Wahrscheinlichkeit für den… …   Deutsch Wikipedia

  • László Lovász — (* 9. März 1948 in Budapest) ist ein ungarischer Mathematiker, der vor allem für seine Arbeiten auf dem Gebiet der Kombinatorik und Graphentheorie bekannt ist …   Deutsch Wikipedia

  • Laszlo Lovasz — László Lovász. László Lovász (* 9. März 1948 in Budapest) ist ein ungarisch amerikanischer Mathematiker, der vor allem für seine Arbeiten auf dem Gebiet der Kombinatorik und Graphentheorie bekannt ist. Inhaltsverzeichnis …   Deutsch Wikipedia

  • 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… …   Deutsch Wikipedia

  • Perfekte Graphen — perfekter Graph Beispiele: Triangulierte Graphen Bipartite Graphen Vollständige Graphen Cographen In der Graphentheorie heißt ein Graph perfekt, wenn für jeden induzierten Subgraphen gilt, dass seine Cliquenzahl mit seiner …   Deutsch Wikipedia

  • Perfekter Graph — Beispiele: Triangulierte Graphen Bipartite Graphen Vollständige Graphen Co Graphen In der Graphentheorie heißt ein Graph perfekt, wenn für jeden induzierten Subgraphen gilt, dass seine Cliquenzahl mit seiner chromatischen Zahl übereinstimmt. Ein… …   Deutsch Wikipedia

  • Matching (Graphentheorie) — Die Theorie um das Finden von Matchings in Graphen ist in der diskreten Mathematik ein umfangreiches Teilgebiet, das in die Graphentheorie eingeordnet wird. Folgende Situation wird dabei betrachtet: Gegeben eine Menge von Dingen und zu diesen… …   Deutsch Wikipedia

  • Kneservermutung — Der Titel dieses Artikels ist mehrdeutig. Das in der Vergangenheit als Kombinatorische Topologie bezeichnete mathematische Fachgebiet findet sich unter Algebraische Topologie. Die Topologische Kombinatorik ist ein jüngeres Fachgebiet der… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”