Beweis von Kőnigs Satz über die Linienfärbung ( $\chi'(G) = \Delta(G)$)
Ich versuche einen Beweis für Kőnigs Satz über die Linienfärbung zu finden , dh:
Der chromatische Index eines zweigeteilten Graphen entspricht seinem maximalen Grad
Zu meiner Überraschung konnte ich jedoch nur zwei Fragen finden, die das Thema berühren:
- Kantenfärbung von zweigeteilten Graphen
- Die Kantenfärbung eines zweigeteilten Graphen mit einem maximalen Grad an D erfordert nur D-Farben
Da Grafiken meine Achillesferse sind, kann ich die oben genannten Informationen nicht zum Nachweis verwenden $\chi'(G) = \Delta(G)$ mich selber.
* Ich habe viele Artikel gefunden, die sich darauf beziehen, aber keine, die dies beweisen, außer Seite 4 von CH6.pdf aus der ersten Frage, aber ich denke nicht, dass dies ausreicht.
Antworten
Ich werde versuchen, einen Überblick über die erforderlichen Kenntnisse zu geben und bei jedem Schritt Quellen anzugeben, damit Sie diese nacheinander verstehen können. Wenn Sie bestimmte Teile nicht verstehen (wie die Konstruktion am Ende), empfehle ich Ihnen, einige kleine Beispiele zu bearbeiten.
Lassen Sie uns zuerst den Satz von Hall vorstellen :
Satz: (Satz von Hall) Let $G$ sei ein zweiteiliger Graph mit Teilen $A$ und $B$. Dann$G$ hat eine passende (unabhängige Kanteneinstellung) Sättigung $A$ (jeder Scheitelpunkt von $A$ ist der Endpunkt einer Kante im Matching) genau dann, wenn für jeden $X \subseteq A$ wir haben $|X| \le |N(X)|$.
Die beiden Quellen, die ich für einen guten Überblick über Halls Theorem empfehle, sind Diestels Graphentheorie (die, wenn ich mich recht erinnere, vier Beweise liefert) und Wests Einführung in die Graphentheorie.
Die Bedeutung von Halls Theorem ist hier die für $k$-regelmäßige zweigeteilte Graphen können wir eine perfekte Übereinstimmung finden. Dies kommt von zwei Dingen:
- EIN $k$-regelmäßiger zweigliedriger Graph ist ausgeglichen .
- EIN $k$-regelmäßiger zweigeteilter Graph erfüllt Halls Bedingung .
Jetzt können wir also Folgendes beweisen:
Lemma: Wenn $G$ ist ein $k$-regelmäßiger zweigliedriger Graph also $\chi'(G) = k$.
Wir können Induktion auf verwenden $k$. Nach dem Satz von Hall,$G$ hat eine perfekte Übereinstimmung $M$. Erwägen$G-M$, welches ist $k-1$-regelmäßig (warum?). Nach der Induktionshypothese$\chi'(G) = k-1$und so können wir hinzufügen $M$ zurück als neue Farbe, wodurch eine richtige erweitert wird $k-1$-edge-Färbung von $G-M$ zu einem richtigen $k$-edge-Färbung auf $G$.
Wenn Sie mit Induktion nicht vertraut sind, finden Sie hier eine andere Beschreibung: Entfernen einer perfekten Übereinstimmung von a $k$-regelmäßiger zweigeteilter Graph ergibt a $k-1$-regelmäßiger Graph, der auch perfekt übereinstimmen muss ... Iterieren Sie diesen Vorgang $k$ mal.
Nun zur Ziellinie. Wir wollen das Ergebnis für jeden zweigeteilten Graphen beweisen$G$.
Ergebnis: Wenn $G$ ist also ein zweiteiliger Graph $\chi'(G) = \Delta(G)$.
Wenn $G$ist regelmäßig, dann sind wir durch das Lemma fertig. Andernfalls gibt es mindestens einen Scheitelpunkt$v$ im $G$ mit $\deg(v) < \Delta(G)$. Wir können ein Diagramm erstellen$R$ so dass
- $R$ ist zweiteilig.
- $R$ ist $\Delta(G)$-regulär.
- $G \subseteq R$.
Eine Konstruktion ist wie folgt. Wir haben$G$ zweiteilig mit Teilen $A$ und $B$. Nehmen Sie eine Kopie von$G$, sagen $G'$ mit Teilen $A'$ und $B'$. Dann für jeden Scheitelpunkt$v$ nicht graduell $\Delta(G)$ im $G$fügen wir eine Kante zwischen $v$ und es ist eine Kopie $v' \in G'$. Dieser neu erhaltene Graph ist zweiteilig mit Teilen$A \cup B'$ und $B \cup A'$. Wiederholen Sie diesen Vorgang nach Bedarf. Sie werden feststellen, dass sich bei jeder Iteration die Lücke zwischen dem minimalen und dem maximalen Grad verringert, sodass wir mit a enden müssen$\Delta(G)$-regelmäßige Grafik $R$wie gewünscht. Sie werden feststellen, dass diese Konstruktion diejenige ist, die Jon Noels Kommentar hier gegeben hat .
Mit dem Lemma, $\chi'(R) = \Delta(G)$und so gibt es eine richtige $\Delta(G)$-edge-Färbung von $R$. Schon seit$G \subseteq R$funktioniert diese richtige Färbung für $G$. Dh$\chi'(G) = \Delta(G)$.
Einige Notizen.
Beachten Sie, dass wir die allgemeine Tatsache verwendet haben, dass $\chi'(H) \le \chi'(G)$ zum $H \subseteq G$ Am Ende.
Eine Sache, über die ich einen Blick geworfen habe, ist, ob wir mehrere Kanten zulassen, aber die Dinge funktionieren immer noch so. Wenn wir mehrere Kanten zulassen, können Sie sehen, warum wir so konstruiert haben$R$ dauert genau $1$Wiederholung? Ich glaube nicht, dass es einen wirklichen Grund gibt, die Verwendung mehrerer Kanten auszuschließen.
Ein wichtiger Aspekt ist, sich Farbklassen in einer Kantenfarbe als das vorzustellen, was sie sind: Übereinstimmungen.