Czy graf k-krytyczne moze byc nieskonczony?

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
kingataranek
Użytkownik
Użytkownik
Posty: 38
Rejestracja: 28 paź 2007, o 12:53
Płeć: Kobieta
Lokalizacja: czestochowa
Podziękował: 5 razy

Czy graf k-krytyczne moze byc nieskonczony?

Post autor: kingataranek » 9 gru 2008, o 14:03

A dokladnie:
Czy graf k-krytyczny moze miec policzlnie nieskonczona liczbe wierzcholkow.
Ja mysle, ze nie moze, ale nie mam pojecia jak to udowodnic.
Prosze o pomoc
Dzieki

xiikzodz
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 4 paź 2008, o 02:13
Płeć: Kobieta
Lokalizacja: Lost Hope
Podziękował: 28 razy
Pomógł: 502 razy

Czy graf k-krytyczne moze byc nieskonczony?

Post autor: xiikzodz » 9 gru 2008, o 15:51

http://renyi.hu/~p_erdos/1951-01.pdf

masz tam fakt (Theorem 1.), z ktorego wynika, ze kazdy graf krytyczny jest skonczony.

kingataranek
Użytkownik
Użytkownik
Posty: 38
Rejestracja: 28 paź 2007, o 12:53
Płeć: Kobieta
Lokalizacja: czestochowa
Podziękował: 5 razy

Czy graf k-krytyczne moze byc nieskonczony?

Post autor: kingataranek » 10 gru 2008, o 00:02

Sorry, ale nie bardzo to jest dla mnie jasne, bo ta teoria mowi o tym ze G nie moze byc (k+1) - colourable, ale przeciez numer chromatyczny moze byc mniejszy od k.
Tzn subgraph moze byc k- colourable ale miec numer chromatyczny 2, a G moze miec numer chromatyczny 3 i wtedy jest krytyczny?

xiikzodz
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 4 paź 2008, o 02:13
Płeć: Kobieta
Lokalizacja: Lost Hope
Podziękował: 28 razy
Pomógł: 502 razy

Czy graf k-krytyczne moze byc nieskonczony?

Post autor: xiikzodz » 10 gru 2008, o 00:16

W twierdzeniu jest wszystko, jak nalezy i trudno o jasniejsze sformulowanie. Jesli bariere stanowi jezyk, to sluze tlumaczeniem:

Twierdzenie 1. Niech \(\displaystyle{ k}\) bedzie liczba naturalna dodatnia i niech graf \(\displaystyle{ G}\) ma te wlasnosc, ze kazdy jego skonczony podgraf jest \(\displaystyle{ k}\)-kolorowalny. Wowczas graf \(\displaystyle{ G}\) jest \(\displaystyle{ k}\)-kolorowalny.

Teza twojego zadania wynika z tego twierdzenia natychmiast. Jesli bowiem graf nieskonczony bylby \(\displaystyle{ k}\)-krytyczny, to kazdy jego podgraf, w tym kazdy jego podgraf skonczony bylby \(\displaystyle{ k-1}\)-kolorowalny i wobec twierdzenia graf \(\displaystyle{ G}\) rowniez, co przeczy jego \(\displaystyle{ k}\)-krytycznosci.

kingataranek
Użytkownik
Użytkownik
Posty: 38
Rejestracja: 28 paź 2007, o 12:53
Płeć: Kobieta
Lokalizacja: czestochowa
Podziękował: 5 razy

Czy graf k-krytyczne moze byc nieskonczony?

Post autor: kingataranek » 10 gru 2008, o 12:55

Dziekuje bardzo

ODPOWIEDZ