Liczba chromatyczna

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11265
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Liczba chromatyczna

Post autor: mol_ksiazkowy »

Udowodnić, że w \(\displaystyle{ n}\) wierzchołkowym grafie regularnym stopnia \(\displaystyle{ d}\) jest \(\displaystyle{ \lambda(G) \geq \frac{n}{n-d} }\). Kiedy może być równość ?
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Liczba chromatyczna

Post autor: arek1357 »

Każdy wierzchołek ma inny kolor niż jego \(\displaystyle{ d}\) sąsiadów, więc co najwyżej \(\displaystyle{ n-d}\) wierzchołków może mieć ten sam kolor.

Kolorów jest:

\(\displaystyle{ \lambda(G)}\)

Więc siłą rzeczy:

\(\displaystyle{ (n-d) \cdot \lambda(G) \ge n}\)

z czego:

\(\displaystyle{ \lambda(G) \ge \frac{n}{n-d} }\)

Dla grafów pełnych na przykład: \(\displaystyle{ d=n-1}\)

\(\displaystyle{ \lambda(G)=n}\)

więc:

\(\displaystyle{ n=n}\)

Lecz nie tylko...
ODPOWIEDZ