Udowodnić, że graf o mniej niż 11 wierzchołkach i bez trójkątów nie ma liczby chromatycznej 4.Własność Grafu
-
mol_ksiazkowy
- Użytkownik
- Posty: 11415
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
Własność Grafu
Udowodnić, że graf o mniej niż 11 wierzchołkach i bez trójkątów nie ma liczby chromatycznej 4.-
arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Własność Grafu
Tak bo ma \(\displaystyle{ 3}\) można to zrobić "organoleptycznie" dla grafu o wierzchołkach: \(\displaystyle{ 9,10}\) i maksymalnych stopniach wierzchołków ale bez trójkątów... raczej działa...
\(\displaystyle{ 9}\) - bo nieparzysta ilość wierzchołków a w nieparzystych zawsze ta liczba chromatyczna się zawyża...
\(\displaystyle{ 10}\) - bo największa ilość wierzchołków
\(\displaystyle{ 9}\) - bo nieparzysta ilość wierzchołków a w nieparzystych zawsze ta liczba chromatyczna się zawyża...
\(\displaystyle{ 10}\) - bo największa ilość wierzchołków