Mathematik: Listenfärbung

Released by matroid on Mi. 12. Januar 2005 23:13:46 [Statistics] Written by Kobe - 2607 x read [Outline] Printer-friendly version -  Choose languageDE EN

\(\begingroup\) Listenfärbung ist ein noch relativ neuer Zweig in der Graphentheorie. Es geht nicht direkt um Färbung von Graphen, mehr um eine Verschärfung des Farbenproblems, mit dem man aber durchaus Probleme lösen kann. Zuerst, was heißt färbbar? [Edit] [To the bottom] Färbbar bedeutet, man färbt eine Ecke mit einer Farbe a und alle adjazenten (benachbarten) Ecken müssen mit einer anderen Farbe als a gefärbt werden. Das kann man als Algorithmus interpretieren, mit dem man (wenn auch erstmal mit sehr vielen Farben) einen Graphen färben kann. Dieser Graph ist dann x-färbbar, wenn man insgesamt x verschiedene Farben genommen hat. [Edit] Was heißt aber Listenfärbung? Man fragt sich, ob ein Graph x-listenfärbbar ist. Rein formal lautet es wie folgt: Man setzt an jede Ecke des Graphen eine Palette bzw. eine Menge von x Farben. Nun muss man überprüfen, ob der Graph mit jeder möglichen Farbbelegung dieser x Farben, färbbar ist. Es reicht wenigstens eine Möglichkeit für jeweils eine Palettenanordnung zu finden, so dass der Graph damit färbbar ist. Ist es nicht möglich den Graph gültig zu färben, bei wenigstens einer Anordnung der Farbpaletten, so ist der Graph nicht x-listenfärbbar. Man beachte, Listenfärbung ist viel stärker als einfache Färbung. Man kann sagen, jeder x-listenfärbbare Graph ist auch x färbbar. Aber nicht, jeder x färbbare Graph ist auch x-listenfärbbar. [Edit] Ein Beispiel: \ Dieser Graph ist offensichtlich 2 färbbar. Sei die erste Farbe \alpha\ und die zweite \beta\ Aber der Graph ist nicht 2-listenfärbbar: Irgendwo muss man anfangen, also sich für eine Farbe entscheiden. Nehmen wir die linke Ecke. Diese erste Ecke färben wir mit \alpha\ => die oberste Ecke muss mit \gamma\ gefärbt werden (da die adjazente Ecke links bereits \alpha\- gefärbt ist) => die rechte Ecke muss mit \delta\ gefärbt werden => die obere mittlere Ecke ist nicht färbbar! \alpha\- und \delta\- gefärbt sind bereits schon adjazente Ecken => die erste Ecke kann man nicht \alpha\ färben Also färben wir die erste Ecke \beta\ => die unterste wird \delta\ gefärbt => die rechte wird \gamma\ gefärbt => die untere mittlere ist nicht färbbar Mehr Möglichkeiten gibt es nicht die erste Ecke zu färben. Also hat man eine Anordnung der Farbpaletten mit sogar 4 verschiedenen Farben gefunden, mit der dieser Graph nicht färbbar ist. Also ist der Graph auch nicht 2-listenfärbbar, obwohl er 2 färbbar ist! [Edit] \(\endgroup\) [Show outline only]

Get link to this article   Printer-friendly version -  Choose languageDE EN     Comments   Für diesen Artikel gibt es keine pdf-Datei

Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:

: Mathematik :: Listenfärbung :: Graphentheorie :: Leicht verständlich : Listenfärbung [von Kobe]

ist ein noch relativ neuer Zweig in der Graphentheorie. Es geht nicht direkt um Färbung von Graphen, mehr um eine Verschärfung des Farbenproblems, mit dem man aber durchaus Probleme lösen kann. Zuerst, was heißt färbbar? [Edit]

[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

Domain	Anzahl	Proz
http://google.de	195	66.1%
https://google.com	33	11.2%
https://google.de	31	10.5%
http://google.fr	29	9.8%
https://duckduckgo.com	3	1%
http://google.com	1	0.3%
https://www.ecosia.org	1	0.3%
https://startpage.com	1	0.3%
https://www.bing.com	1	0.3%

[Top of page]