Twierdzenie o minimalnym stopniu w grafie k-krytycznym

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Majeskas
Użytkownik
Użytkownik
Posty: 1456
Rejestracja: 14 gru 2007, o 14:36
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 49 razy
Pomógł: 198 razy

Twierdzenie o minimalnym stopniu w grafie k-krytycznym

Post autor: Majeskas »

Znalazłem to zadanie między innymi pod taką nazwą jak w temacie. Należy pokazać, że każdy wierzchołek w grafie \(\displaystyle{ k}\)-krytycznym (tzn. takim, że \(\displaystyle{ \chi(G)=k}\) i usunięcie jakiegokolwiek wierzchołka zmniejsza liczbę chromatyczną) ma stopień równy co najmniej \(\displaystyle{ k-1}\).
Downonmyluck
Użytkownik
Użytkownik
Posty: 44
Rejestracja: 25 kwie 2015, o 12:24
Płeć: Mężczyzna
Podziękował: 11 razy
Pomógł: 3 razy

Twierdzenie o minimalnym stopniu w grafie k-krytycznym

Post autor: Downonmyluck »

Zauważ, że każdy wierzchołek danego koloru musi być połączony z jakimkolwiek wierzchołkiem o innym kolorze. W przeciwnym razie można byłoby znaleźć lepsze kolorowanie. Tak więc tych kolorów (poza kolorem, którym pokolorwany jest rozpatrywany wierzchołek) jest \(\displaystyle{ k-1}\). Można też zrobić to nie wprost i wykorzystać k-krytyczność.

Niech \(\displaystyle{ v \in V}\) będzie wierzchołkiem o najmniejszym stopniu i załóżmy, że \(\displaystyle{ \delta(G) < k-1}\).
Wtedy liczba chromatyczna \(\displaystyle{ G-v}\) wynosi \(\displaystyle{ k-1}\) i oznaczmy zbiór kolorów \(\displaystyle{ A = \left\{ 1,2,...,k-1\right\}}\). Widać, że z zasady szufladkowej istnieje taki kolor \(\displaystyle{ j \in A}\), którym nie został pokolorowany żaden z wierzchołków incydentych z \(\displaystyle{ v}\). W takim razie kolorując \(\displaystyle{ v}\) kolorem \(\displaystyle{ j}\) otrzymujemy dobre pokolorowane grafu \(\displaystyle{ G}\) na \(\displaystyle{ k-1}\) kolorów. Sprzeczność.
Ostatnio zmieniony 2 wrz 2016, o 21:45 przez Downonmyluck, łącznie zmieniany 4 razy.
Mruczek
Użytkownik
Użytkownik
Posty: 1114
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 157 razy

Twierdzenie o minimalnym stopniu w grafie k-krytycznym

Post autor: Mruczek »

Dowód nie wprost. Załóżmy, że w tym grafie istnieje wierzchołek stopnia mniejszego niż \(\displaystyle{ k - 1}\). Z założenia jego usunięcie zmniejsza liczbę chromatyczną, czyli liczba chromatyczna grafu bez tego wierzchołka jest nie większa niż \(\displaystyle{ k - 1}\). Jest on połączony z co najwyżej \(\displaystyle{ k - 2}\) innymi wierzchołkami, więc można go pokolorować pozostałym \(\displaystyle{ k - 1}\)-szym kolorem, więc cały graf ma liczbę chromatyczną nie większą niż \(\displaystyle{ k - 1}\), sprzeczność.
Majeskas
Użytkownik
Użytkownik
Posty: 1456
Rejestracja: 14 gru 2007, o 14:36
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 49 razy
Pomógł: 198 razy

Twierdzenie o minimalnym stopniu w grafie k-krytycznym

Post autor: Majeskas »

Dziękuję za odpowiedzi, i to tak szybkie. Właściwie nie było to trudne. Za szybko się zniechęciłem.
Downonmyluck pisze:Zauważ, że każdy wierzchołek danego koloru musi być połączony z jakimkolwiek wierzchołkiem o innym kolorze. W przeciwnym razie można byłoby znaleźć lepsze kolorowanie. Tak więc tych kolorów (poza kolorem, którym pokolorwany jest rozpatrywany wierzchołek) jest \(\displaystyle{ k-1}\). Można też zrobić to nie wprost i wykorzystać k-krytyczność.
Nie całkiem rozumiem. Chciałeś chyba powiedzieć tyle, że przy optymalnym kolorowaniu dla każdej pary kolorów istnieje krawędź, której końce są pomalowane tymi kolorami. Ale dlaczego "tych kolorów jest \(\displaystyle{ k-1}\)"? Tzn. właściwie których? Brzmi to tak, jakbyś podał jakiś pierwszy sposób rozwiązania, nie wykorzystujący \(\displaystyle{ k}\)-krytyczności. Jakoś tego nie widzę.
Niech \(\displaystyle{ v \in V}\) będzie wierzchołkiem o najmniejszym stopniu i załóżmy, że \(\displaystyle{ \delta(G) < k-1}\).
Wtedy liczba chromatyczna \(\displaystyle{ G-v}\) wynosi \(\displaystyle{ k-1}\) i oznaczmy zbiór kolorów \(\displaystyle{ A = \left\{ 1,2,...,k-1\right\}}\). Widać, że z zasady szufladkowej istnieje taki kolor \(\displaystyle{ j \in A}\), którym nie został pokolorowany żaden z wierzchołków incydentych z \(\displaystyle{ v}\). W takim razie kolorując \(\displaystyle{ v}\) kolorem \(\displaystyle{ j}\) otrzymujemy dobre pokolorowane grafu \(\displaystyle{ G}\) na \(\displaystyle{ k-1}\) kolorów. Sprzeczność.
OK, przy czym zgodziłbym się raczej z Mruczkiem, że po wycięciu \(\displaystyle{ v}\) liczba chromatyczna jest równa co najwyżej \(\displaystyle{ k-1}\), a nie dokładnie \(\displaystyle{ k-1}\).
Downonmyluck
Użytkownik
Użytkownik
Posty: 44
Rejestracja: 25 kwie 2015, o 12:24
Płeć: Mężczyzna
Podziękował: 11 razy
Pomógł: 3 razy

Twierdzenie o minimalnym stopniu w grafie k-krytycznym

Post autor: Downonmyluck »

Majeskas pisze:
Nie całkiem rozumiem. Chciałeś chyba powiedzieć tyle, że przy optymalnym kolorowaniu dla każdej pary kolorów istnieje krawędź, której końce są pomalowane tymi kolorami. Ale dlaczego "tych kolorów jest \(\displaystyle{ k-1}\)"? Tzn. właściwie których? Brzmi to tak, jakbyś podał jakiś pierwszy sposób rozwiązania, nie wykorzystujący \(\displaystyle{ k}\)-krytyczności. Jakoś tego nie widzę.
Przepraszam, napisałem bzdurę. Miałem w głowie nierówność \(\displaystyle{ e(G) \ge {k \choose 2}}\), gdzie \(\displaystyle{ k}\) jest liczbą chromatyczną. Innymi słowy między dowolnymi zbiorami niezależnych wierzchołków (gdzie są one pokolorowane tym samym kolorem) musi istnieć co najmniej jedna krawędź, inaczej moglibyśmy zdefiniować lepsze kolorowanie.
ODPOWIEDZ