2-f. Zushg. in kritischemGraph < Sonstiges < Hochschule < Mathe < Vorhilfe
|
Hallo Mathefreunde,
ich habe ein Problem, das ich nicht lösen kann, auch wenn es nach dem zugrundeliegenden Paper "obvious" sei.
Gegeben sei ein Graph mit maximalem Eckengrad [mm] \Delta, [/mm] und er habe eine echte Totalfärbung mit [mm] \Delta [/mm] + 3 Farben; also [mm] \chi_T(G) [/mm] = [mm] \Delta [/mm] + 3.
Der Graph sei bzgl. [mm] \chi_T(G) [/mm] minimal, d.h., wenn ich eine Ecke oder Kante wegnehme, hat der Graph eine echte Totalfärbung mit [mm] \Delta [/mm] + 2 Farben. [mm] (\Delta [/mm] ist hier speziell gleich 6 und der Graph sei zudem planar und zwei Dreiecke haben keine gemeinsame KAnte, aber das ist wohl nicht von Bedeutung hier)
Wieso ist ein solcher minimaler Graph 2-fach zusammenhängend?
Also hier steht "obvious"; aber leider nicht für mich.
Einfacher Zusammenhang ist klar.
Aber bei dem zweifachen Zusammenhang komme ich nicht auf die Lösung und das mehreren Ansätzen eines indirekten Beweises.
Ich nehme an, er ist 1-fach zshgd., dann ex. eine Schnittecke v.
G-v hat dann eine Totalfärbung mit [mm] \Delta [/mm] + 2 Farben und G-v zerfällt in ein paar Komponenten (höchstens [mm] \Delta). [/mm] Ich nehme die Ecke und die Kanten, die ich rausgenommen habe hinzu und habe zunächst eine Teilfärbung mit [mm] \Delta [/mm] + 2 Farben. Dann kann ich die Schnittecke locker färben, denn ich habe dafür mindestens 2 Farben zur Verfügung. Eine der ungefärbten Kanten kann ich dann auch noch färben, aber wie sieht es aus für alle anderen Fälle? Wie sähe dort eine etwaige Umfärbung aus?
Oder geht der Beweis kürzer?
Ich habe auch angesetzt mit: Wenn G 1-fach zshg., ex. min. eine Kante, die nicht auf einem Kreis liegt. Füge ich eine Kante hinzu derart, dass diese Kante nachher auf einem Kreis liegt und die hinzugefügte Kante, die färbe ich mit einer der [mm] \Delta [/mm] + 2 Farben, ohne die Echtheit zu verletzten, dann wäre ich auch fertig. Aber das ist nicht so leicht.
Ich bitte echt um Hilfe...
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:21 Mi 01.07.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
