Proszę o rzucenie okiem:
\(\displaystyle{ X(G) \le 4 \Rightarrow G}\) planarny
Kontrprzykład :
Liczba chromatyczna grafu \(\displaystyle{ K_{5}}\) wynosi \(\displaystyle{ 4}\),a \(\displaystyle{ K_{5}}\) nie jest planarny.
Dawno nie trafiło mi się podchwytliwe zadanie, dlatego chcę się upewnić.
Planarność grafu
-
- Użytkownik
- Posty: 59
- Rejestracja: 2 gru 2014, o 18:25
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 17 razy
Planarność grafu
Z tw. Brooksa liczba chromatyczna \(\displaystyle{ K_{5}}\) wynosi \(\displaystyle{ 5}\), bo \(\displaystyle{ \Delta = 4}\) i graf jest grafem pełnym, więc \(\displaystyle{ X(G) =\Delta + 1 = 5}\).
Planarność grafu
No właśnie, wrócę do tego jutro bo dzisiaj już padam. Czyli trzeba ugryźć to inaczej-- 19 sie 2015, o 10:45 --Zaraz zaraz,ale liczba chromatyczna grafu \(\displaystyle{ K_{3,3}}\) wynosi \(\displaystyle{ 2}\) a on na pewno nie jest planarny.