Suma liczb chromatycznych dowolnego grafu i jego dopełnienia
-
- Użytkownik
- Posty: 16
- Rejestracja: 14 paź 2020, o 23:37
- Płeć: Mężczyzna
- wiek: 20
- Podziękował: 4 razy
Suma liczb chromatycznych dowolnego grafu i jego dopełnienia
W jaki sposób można udowodnić (lub pokazać, że to nie zachodzi), że $$\chi(G) + \chi(\overline{G}) \geq n$$gdzie G to dowolny graf o n-wierzchołkach?
- kerajs
- Użytkownik
- Posty: 8581
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3349 razy
Re: Suma liczb chromatycznych dowolnego grafu i jego dopełnienia
Może tak:
Wybieram dowolny wierzchołek. Jest on stopnia \(\displaystyle{ k }\), gdzie \(\displaystyle{ k \in \left\{ 0,1,..., n-1\right\} }\) więc liczba barw potrzebna do pokolorowania tego wierzchołka i wierzchołków z którymi jest połączony wynosi \(\displaystyle{ k+1}\), a stąd \(\displaystyle{ \chi(G) \ge k+1}\) .
W grafie dopełniającym ten sam wierzchołek jest stopnia \(\displaystyle{ n-1-k}\), więc \(\displaystyle{ \chi(\overline{G}) \ge n-1-k+1}\) .
Wychodzi ciut mocniejsza teza:\(\displaystyle{ \chi(G) + \chi(\overline{G}) \ge n+1 }\)
Jest tak dlatego, iż założyłem że graf ma więcej niż jeden wierzchołek (wybrany wierzchołek ma sąsiadów z którymi jest lub nie jest połączony), i dla takich grafów będzie ona prawdziwa.
Dołóż przypadek \(\displaystyle{ n=1}\) a otrzymasz tezę z zadania.
Wybieram dowolny wierzchołek. Jest on stopnia \(\displaystyle{ k }\), gdzie \(\displaystyle{ k \in \left\{ 0,1,..., n-1\right\} }\) więc liczba barw potrzebna do pokolorowania tego wierzchołka i wierzchołków z którymi jest połączony wynosi \(\displaystyle{ k+1}\), a stąd \(\displaystyle{ \chi(G) \ge k+1}\) .
W grafie dopełniającym ten sam wierzchołek jest stopnia \(\displaystyle{ n-1-k}\), więc \(\displaystyle{ \chi(\overline{G}) \ge n-1-k+1}\) .
Wychodzi ciut mocniejsza teza:\(\displaystyle{ \chi(G) + \chi(\overline{G}) \ge n+1 }\)
Jest tak dlatego, iż założyłem że graf ma więcej niż jeden wierzchołek (wybrany wierzchołek ma sąsiadów z którymi jest lub nie jest połączony), i dla takich grafów będzie ona prawdziwa.
Dołóż przypadek \(\displaystyle{ n=1}\) a otrzymasz tezę z zadania.
- mol_ksiazkowy
- Użytkownik
- Posty: 11367
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Re: Suma liczb chromatycznych dowolnego grafu i jego dopełnienia
No ale np. drzewa są \(\displaystyle{ 2 }\) chromatyczne, a mogą mieć wierzchołki większych stopni...itd.Wybieram dowolny wierzchołek. Jest on stopnia \(\displaystyle{ k }\), gdzie \(\displaystyle{ k \in \left\{ 0,1,..., n-1\right\} }\) więc liczba barw potrzebna do pokolorowania tego wierzchołka i wierzchołków z którymi jest połączony wynosi \(\displaystyle{ k+1}\), a stąd \(\displaystyle{ \chi(G) \ge k+1}\) .
- mol_ksiazkowy
- Użytkownik
- Posty: 11367
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Re: Suma liczb chromatycznych dowolnego grafu i jego dopełnienia
A co gdy graf jest dwudzielny \(\displaystyle{ K_{n,n }}\) ?
- arek1357
- Użytkownik
- Posty: 5740
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 razy
Re: Suma liczb chromatycznych dowolnego grafu i jego dopełnienia
Tu jest prosty dowód niby czegoś prawie odwrotnego:
Grafy-liczba chromatyczna, dopełnienia i dwudzielność
Grafy-liczba chromatyczna, dopełnienia i dwudzielność
- kerajs
- Użytkownik
- Posty: 8581
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3349 razy
Re: Suma liczb chromatycznych dowolnego grafu i jego dopełnienia
Zgrabny kontrprzykład.mol_ksiazkowy pisze: ↑9 gru 2020, o 09:14
A co gdy graf jest dwudzielny \(\displaystyle{ K_{n,n }}\) ?
- mol_ksiazkowy
- Użytkownik
- Posty: 11367
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Re: Suma liczb chromatycznych dowolnego grafu i jego dopełnienia
?$$\chi(G) \chi(\overline{G}) \geq n$$
Ukryta treść: