k-Färbbarkeit eines Subgraphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Es sei G ein Graph mit e(G) Kanten und k >= 2 eine ganze Zahl. Zeigen sie, dass es einen k-partiten Subgraphen von G' [mm] \subseteq [/mm] G gibt, sodass e(G') >= [mm] \bruch{k-1}{k}e(G). [/mm] |
Hi,
ich komme leider nicht weiter. Ich habe mir überlegt dies mit Induktion zu lösen, da wir bereits bewiesen haben dass jeder Graph einen bipartiten Subgraphen mit mindestens halb so vielen Kanten wie der ursprüngliche Graph besitzt, wäre der Induktionsanfang für k=2 gelöst.
Die Induktivorrausetzung, sei, dass obige Gleichung für alle k >= gilt.
Induktionsschritt: Gesucht wird ein k+1 färbbarer Subgraph von G mit gewünschter Eigenschaft.
Nach Induktionsvorraussetzung gibt es einen k-färbbaren Subgraphen mit gewünschter Eigenschaft.
Sei dieser k färbbare Subgraph G' maximal, d.h. hinzufügen eines weiteren Knotens aus G führt dazu, dass G' nicht mehr k färbbar ist.
Füge man also so einen Knoten hinzu, dann muss dieser mindesten k Kanten erhalten, damit G' nicht mehr k färbbar ist(mit jeder Farbe einmal verbunden).
Dann gilt e(G') + k >= [mm] \bruch{k-1}{k}e(G) [/mm] + k.
Weiter komme ich nicht. Ist mein Ansatz richtig.
Schoneinmal Danke im Vorraus
Grüße MeineKekse
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Mo 10.02.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
