fast-trianguliert:
fast-triangulierter Graph: Ein zusammenhaengeder Graph, bei dem alle beschraenkten Gebiete werden durch Einbettung von Dreiecken gegrenzt
Hinzufuegen von Kanten: Listenchronomatische Zahl kann allenfalls vergroessert werden
chronomatisch: Faerbung
Listen-chronomatisch: Man faerbt mit einer ganzen Liste. Aehnlich wie bei Computer Bilddateien, gibt es eine Tabelle. Und es gibt fuer jeden Knoten
eine Liste, von moeglichen, die mit den Farben der anderen Knoten disjunkt ist
Uebung, Zeichne fast-triangulierte Graphen, neue Uebung, jeden Tag fast triangulierte Graphen
Uebung: Zeichne Graphen mit Valenz 2 pro Knoten und Faerbe den, fuege mehrere Kanten und faerbe die Knoten, um zu sehen, die listen-chronomatische
Zahl steigt
listen-chronomatisch falsch definiert: Das ist keine Liste von Farben fuer einen Knoten, sondern fuer einen Knoten existiert eine Menge
$C(v)$ von Farben. Und die Listenfaerbung ist die Vereinigung dieser Farben fuer alle Knoten
Das Dinitz Problem, Kapital 26
Biparater Graph, stabiles Matching
Listen-chronomatisch:
Angenommen im Graphen $G=(V,E)$ ist fuer jede Ecke eine Menge $C(v)$ von Farben gegeben
Eine Listenfaerbung ist eine Faerbung $c:V\to \cup_{v\in V}C(v)$
Listenchronomatische Zahl $X_l(G)$ ist die kleinste Zahl $k$. dass fuier jede Liste von Farbmengen immer eine Listenfaerbung existiert.
\begin{enumerate}
\item Farbe
\item Listenfaerbung
\item Listenchronomatische Zahl
\end{enumerate}
Also, wie bei der Fernuni Hagen, hinzufuegen von Kanten
Das Hinzufuegen von Kanten, kann die Listenchronomatische Zahl allenfalls vergroessern
Jetzt unterschied
Triangulierte Graph
Fast Triangulierter Graph
Triangulierte Graph: Ueben Zeichnnen, besteht aus lauter Dreiecken
Fast Trianguliert, wird durch einen Kreis begranzt,
Fast-trianguliert = Dreiecksgraph
Chordalen Graphen: alles dreieck
Dreiecksgraph: Fast Trianguliert
Kommando zurueck, Denkfehler, ich habe gerade jeden Knoten mit mehr als 3 Kanten gesehen. Also habe ich was falsches gedacht
Jedes Gebiet ist ein Dreieck das haengt von der Valenz ab
Beispiel wir machen zwei Dreiecke mit einem Scheitelpunkt nebeneinander, dann sind das trotzdem dreiecke, es geht um die Gebiete
Also, jetzt aeusserer Kreis B, das ist logisch
Kreis der Graphentheorie v0e1v1e2...v0
Und das jetzt der aeusserste Kreis
Annahme
Zwei benachbarte Ecken auf B sind bereits mit verschiedenen Farben $\alpha$ und $\beta$ gefaerbt
Das steht mir zu, auf dem ausseren Kreis. Auf dem aeusseren Kreis, hat jeder Valenz 2, das heisst, ich kann abwechselnd machen, halt nur fuer die Benachbarten
C(v) \ge 3
Fuer alle anderen Ecken von v von B
Das steht mir auch zu, ich kann abwechselnd machen, aber ich kann sagen,
\ge geht immer. Und wenn ich 2 Minimum groesser gleich 3, fuer alle im Kreis geht
letzte Annahme, fuer alle groesser gleich 5
|V| = 3, dafuer offensichtlich
Klar, bei 3 Knoten brauche ich nicht mehr als 3 Farben
OK, wenn der Graph nicht fast trianguliert ist, sieht es so aus, er ist nicht mehr planar
Das erste, was wir wissen muessen, ist dass der Graph
fast trianguliert ist
Von einem Kreis B umgeben ist
Ich stelle mir das so vor. Ein Dreieck kann in jedem Fall mit drei Gefuellt werden
Ich habe den Kreis B vom graphen
Dadurch geht eine Sehne durch den Kreis, der Teilt den Kreis in zwei Haelften
Dann ist die eine Haelfte Fasttrianguliert
und die andere
Nach der Induktion gilt fuer beide, das gleiche, wie vorher, jetzt geht die Teilung Induktion, und es geht immer weiter, bis ich bei Induktionsanfang
dem einzelnen Dreeick herauskomme. Hier gilt, dass drei Farben reichen, Das Induktionsanfang unser Dreieck
Jetzt halt, nicht ganz richtig, Das aussere mit der Sehne bildet ein Dreieck
|C(v)| \ge 3 fuer alle Ecken $v$ auf $B$
Das heisst, der Induktionsanfang bezieht sich auf das aeussere Dreieck
