Liczba i indeks chromatyczny grafu

Szemek · Post autor: **Szemek** » 26 cze 2009, o 23:43

Zadanie pochodzi z mojego (zaliczonego ) egzaminu z dyskretnej.
Dla rozruszania szarych komórek

Określ liczbę chromatyczną grafu \(\displaystyle{ G}\) rzędu \(\displaystyle{ n}\), \(\displaystyle{ n\ge 3}\) otrzymanego z grafu pełnego \(\displaystyle{ K_n}\) poprzez usunięcie jednej krawędzi. Ile wynosi indeks chromatyczny grafu \(\displaystyle{ G}\).

miodzio1988 · Post autor: **miodzio1988** » 27 cze 2009, o 00:07

W grafie pełnym \(\displaystyle{ K_{n}}\)liczba chromatyczna wynosi \(\displaystyle{ n-1}\). Usuwając dowolną krawędź dostajemy dwa wierzchołki, które nie sąsiadują ze sobą (inne wierzchołki dalej mają tych samych sąsiadów itd ) . Te dwa wierzchołki kolorujemy na ten sam kolor. Zatem liczba chromatyczna grafu \(\displaystyle{ K_{n}}\) jest równa \(\displaystyle{ n-2}\)
ZA ŁATWO mi to przyszło i szukam jakiegoś haczyka

Indeks chromatyczny grafu pełnego \(\displaystyle{ K_{n}}\) wynosi \(\displaystyle{ n-1}\) dla n parzystych i \(\displaystyle{ n}\) dla n nieparzystych. (dowód podawać? ) I usunięcie jednej krawędzi nam niczego nie zmieni...(i tego nie jestem pewny )
Sprawdź czy do tej pory jest dobrze
Bo nie wiem czy w dobrym kierunku idę

Edit
\(\displaystyle{ K_{3}}\) dla tego grafu się jednak zmieniło więc trzeba pomyślec

Szemek · Post autor: **Szemek** » 27 cze 2009, o 00:20

Jest ok.
Udało Ci się wyłapać haczyk dla indeksu chromatycznego

miodzio1988 · Post autor: **miodzio1988** » 27 cze 2009, o 00:21

Czyli jest dobrze?
Bo aż uwierzyć nie mogę

Szemek · Post autor: **Szemek** » 27 cze 2009, o 00:22

Jest dobrze.
Twoja kolej na zadanie.

xiikzodz · Post autor: **xiikzodz** » 27 cze 2009, o 00:29

W pierwszej części odpowiedź \(\displaystyle{ |G|-1}\). Ograniczenie z dołu otrzymujemy wskazując kolorowania, z góry zauważając, że \(\displaystyle{ K_n}\) bez krawędzi zawiera \(\displaystyle{ K_{n-1}}\).

W drugim z dołu ograniczamy przez minimalny stopień wierzchołka, a z góry przez indeks chromatyczny grafu przed operacją. Te liczby są równe, jeśli wyłączyć 3, który rozważamy oddzielnie.

Szemek · Post autor: **Szemek** » 27 cze 2009, o 00:51

xiikzodz, dzięki
chyba lepiej pójdę już spać

sopi · Post autor: **sopi** » 27 cze 2009, o 22:23

hmmm, a czy w grafie pełnym\(\displaystyle{ K_{n}}\) liczba chromatyczna nie wynosi przypadkiem \(\displaystyle{ n}\) ??

miodzio1988 · Post autor: **miodzio1988** » 27 cze 2009, o 22:29

sopi pisze:hmmm, a czy w grafie pełnym\(\displaystyle{ K_{n}}\) liczba chromatyczna nie wynosi przypadkiem \(\displaystyle{ n}\) ??

Przykro mi, ale nie. Zerknij na def liczby chromatycznej.

xiikzodz · Post autor: **xiikzodz** » 27 cze 2009, o 22:36

Może masz gdzieś link do definicji? Moja jest z książki Wilsona i \(\displaystyle{ \chi(K_n)=n}\).

miodzio1988 · Post autor: **miodzio1988** » 27 cze 2009, o 22:39

xiikzodz pisze:Może masz gdzieś link do definicji? Moja jest z książki Wilsona i \(\displaystyle{ \chi(K_n)=n}\).

Ups Przyznaję się zatem do błędu

sopi · Post autor: **sopi** » 27 cze 2009, o 22:42

Wilson ...

Kamila_88 · Post autor: **Kamila_88** » 14 wrz 2009, o 11:14

w takiej sytuacji rozwiązanie różni się tylko zamianą n-1 na n czy cos wiecej?