Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » chromatische Zahl Abschätzung
Autor
Universität/Hochschule chromatische Zahl Abschätzung
NewbieNew
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 17.11.2013
Mitteilungen: 106
  Themenstart: 2021-11-25

Hallo, ich gehe gerade das Paper "chromatic number of P_5-free graphs: Reed's Conjecture" durch. Ich hänge an einem Beweis (Theorem 9) bei dem wir einen (P_5, Gem+)-freien Graphen in (nicht notwenigerweise disjunkte) Teilgraphen aufteilen. Unter anderem betrachten wir den Graphen, der von \[N^0:=\{v\in V(G)\backslash D\mid D \subseteq N(v)\}\] induziert wird (D ist hier eine dominierende Clique der Größe t). Wenn ich das richtig verstehe, dann existiert \(N^0\) nur, falls D nicht die _größte_ dominierende Clique ist. Wir wollen jetzt \(\chi(G[N^0])\) abschätzen. Laut Paper gilt \[\chi(G[N^0])\leq(\omega(G)-t)^2 \:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\: (1)\] Zu sagen ist noch, dass wir durch Induktion beweisen und haben als IA gezeigt, dass für \(\omega(G)=2\) gilt: \(\chi(G)\leq \omega^2(G)\) Meine Vermutung ist nun, dass wir auf (1) die Induktionsvoraussetzung anwenden. Dass \(\chi(G[N^0])\) maximal Cliquenzahl $\omega(G)-t$ besitzt ist mir klar. Nur hänge ich an der Induktionsvoraussetzung. So wie ich Induktion kennen gelernt habe (bzw wie ich es noch im Kopf habe), können wir nur eine Aussage über einen Graphen mit Cliquenzahl $\omega(G)-1$ treffen. Wenn wir eine Aussage über einen Graphen mit Cliquenzahl $\omega(G)-t$ treffen wollen, so müssten wir doch als Induktionanfang t verschiedene Rechnungen zeigen und zwar für Graphen mit Cliquenzahl 1 (trivial), 2 usw bis t. Kann mir jemand helfen und sagen wo mein Gedankenfehler liegt? (Das scheint mir wie eine sehr simple Frage. Alle anderen 'komplizierteren' Schritte sind verständlich, aber da hänge ich nun.. Naja) Lieben Dank :)


Wahlurne Für NewbieNew bei den Matheplanet-Awards stimmen
   Profil
NewbieNew
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 17.11.2013
Mitteilungen: 106
  Beitrag No.1, vom Themenstarter, eingetragen 2021-11-27

Hat keiner eine Idee?


Wahlurne Für NewbieNew bei den Matheplanet-Awards stimmen
   Profil

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]