Graphentheorie: Satz zur Taillenweite |
| 03.09.2007, 15:58 | Mattim | Auf diesen Beitrag antworten » |
| Graphentheorie: Satz zur Taillenweite Lemma 8: Der folgende Untergraph ist 6-reduzierbar* in Graphen mit einer Taillenweite** von mindestens 6: -ein Kreis der Länge 3, der zwei Ecken vom Grad 3 und eine Ecke vom Grad 1 enthält. Das wird nun u.a. für den Kreis bewiesen. Nur: ist es nicht klar, dass ein Kreis der Länge 3 nicht in einem Graphen mit einer Taillenweite von min 6 vorkommen kann???? 
*6-reduzierbar: kann nicht in einem 6-minimalen Graphen vorkommen -6-minimaler Graph: Das Quadrat des Graphen ist nicht 6-färbbar, aber die Quadrate jedes Untergraphen sind 6-färbbar -Quadrat eines Graphen: Im Quadrat eines Graphen werden auch die Ecken verbunden, die einen Abstand von 2 haben **Taillenweite: Länge des kürzesten Kreises in G. den ganzen Artikel gibts unter http://iti.mff.cuni.cz/iti-old/series/files/iti255.pdf Der Beweis ist auf Seite 12. Danke Matti |
||
| 05.09.2007, 10:03 | Mattim | Auf diesen Beitrag antworten » |
hat keiner eine idee? 
|
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
