Liczba chromatyczna
- mol_ksiazkowy
- 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
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ść ?
- arek1357
- 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
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...
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...