Planarer Graph als kantendisjunkte Vereinigung dreier Wälder

13/02/2008 - 12:41 von lhallwass | Report spam
Guten Tag,

Gezeigt werden soll, dass jeder planare Graph eine kantendisjunkte
Vereinigung dreier Wàlder (= kreisfreier Graphen) ist.

Das ist gleichbedeutend mit der Frage, ob man die Kanten so mit drei
Farben fàrben kann, dass kein gleichfarbiger Kreis entsteht.

Leider fehlt mir dazu die passende Beweisidee. Eine Reduktion auf die
Vierfàrbbarkeit der Knoten ist mir nicht gelungen.

(Man kann sicher davon ausgehen, dass der Graph maximal planar ist.)
 

Lesen sie die antworten

#1 Philipp Zumstein
14/02/2008 - 09:44 | Warnen spam
schrieb:
Gezeigt werden soll, dass jeder planare Graph eine kantendisjunkte
Vereinigung dreier Wàlder (= kreisfreier Graphen) ist.



Dies wird auch (edge-)arboricity genannt.

Das ist gleichbedeutend mit der Frage, ob man die Kanten so mit drei
Farben fàrben kann, dass kein gleichfarbiger Kreis entsteht.

Leider fehlt mir dazu die passende Beweisidee. Eine Reduktion auf die
Vierfàrbbarkeit der Knoten ist mir nicht gelungen.

(Man kann sicher davon ausgehen, dass der Graph maximal planar ist.)



Ist dies eine Übungsaufgabe? Falls ja, könnte es hilfreich sein, zu
wissen, welche Begriffe und Sàtze in der Vorlesung gezeigt wurden. Falls
nein, kann man sich einen Standardbeweis über Matroidentheorie anschauen.

Grüsse,
Philipp

Ähnliche fragen