Mam taki problem:
pokazać, że indeks chromatyczny dla Grafu Petersena wynosi 4 a nie 3
Można rozpatrzyć różne przypadki, ale ma być ich minimalna liczba (tam chyba podobno można to zmniejszyć do 3 lub 4...), chyba, że znacie jakiś inny dowód
Pozdrawiam
[ Dodano: 12 Czerwca 2007, 21:10 ]
Wystarczy rozpatrzyć "zewnętrzny" cykl kolorując go (gwiazde na razie olewamy) i zauważyć, że jak go nie pokolorujemy będzie on zawsze identycznie pokolorowany (z dokładnością do użytych kolorów, jednak układ jest zawsze identyczny tj. (idąc po obwodzie) 12313 ) następnie pokolorować oczywiste wypustki (te łączące gwiazdę z obwodem) i zauważyć, że nie możliwe już jest użycie tylko trzeciego koloru do pokolorowania gwiazdy gdyż następuje kolizja
Pozdrawiam
p.s. głupio odpowiadać na własnego posta, ale może ktoś spotka się z tym problemem a już go rozwiązałem