?l(Sn) ? n + 1 Beweis von Janssen |
| 03.03.2013, 21:24 | Mathebiene7717 | Auf diesen Beitrag antworten » |
| ?l(Sn) ? n + 1 Beweis von Janssen Hey ihr lieben, habe ein Problem bei diesem Beweis: ?l(Sn) ? n + 1. Bei ?l handelt es sich um die Listenchromatische Zahl. Habe absolut keine Ahnung wie der Beweis aussehen könnte. Ich hoffe, dass ihr mir weiterhelfen könnt. Liebe Grüße Meine Ideen: Die listenchromatische Zahl eines Graphen ist dann die minimale Listenlänge n, so dass für beliebige vorgegebene Färblisten mit jeweils n Elementen an den Knoten eines Graphen eine gültige Lsitenfärbung existiert. Insbesondere existiert dann eine Listenfärbung, wenn man alle Listen aus den gleichen n Elementen bestehen lässt - das ist eine normale n-Färbung, also ist die listenchromatische Zahl nicht kleiner als die chromatische Zahl. Und Sn ist der Graph der als Eckenmenge die n² Felder eines (n x n)-Quasdrats hat wobei zwei felder genau dann benachbart sind,wenn sie in derselben zeile oder spalte auftreten |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
