a) Egy $G$ gráfban 1000 darab csúcstól eltekintve minden pont foka legfeljebb 999. Bizonyítsuk be, hogy a gráf kromatikus száma legfeljebb 1000.
b) Egy $G$ gráf csúcshalmaza legyen a $V(G)=\{1,2,3,\dots,30\}$ és két csúcs akkor legyen szomszédos, ha a különbségük legalább 6. Mekkora ennek a gráfnak a kromatikus száma?
Egy 1001 csúcsú gráf úgy keletkezik, hogy egy 1000 csúcsot tartalmazó kör minden pontját összekötjük az 1001-edik csúccsal. Mekkora ennek a gráfnak az élkromatikus száma?
a) Egy 2000 csúcsú G gráf két darab egyenként 1000 csúcsot tartalmazó körből készítettünk, úgy, hogy az egyik kör minden csúcsát összekötöttük a másik kör minden csúcsával.
Mekkora az így keletkező G gráf kromatikus száma és élkromatikus száma?
b) Számoljuk ki a Petersen gráf kromatikus számát.
c) Egy $G$ gráf csúcshalmaza legyen $V(G)=\{ 1,2,3,\dots, 30 \} $ és két csúcs akkor legyen szomszédos, ha a számok távolsága legalább 5. Mekkora ennek a gráfnak a kromatikus száma?
d) Egy másik gráf csúcshalmaza szintén a $V(G)=\{ 1,2,3,\dots, 30 \} $. A gráf $x,y \in V(G)$ csúcsai pontosan akkor legyenek szomszédosak, ha $ \mid x -y \mid = 4$ vagy $ \mid x - y \mid =6$. Határozzuk meg a gráf kromatikus számát.
a) A $G$ gráf csúcshalmaza legyen a $V(G)=\{ 1, 2, 3, \dots, 30 \}$. Az $x,y \in V(G)$ csúcsok pontosan akkor legyenek szomszédosak $G$-ben, ha $ \mid x -y \mid = 3$ vagy $\mid x -y \mid = 5$. Határozzuk meg a $G$ gráf $\chi{(G)}$ kromatikus számát és $\chi_e{(G)}$ élkromatikus számát.
b) Egy 20 csúcsú fában 11 csúcs foka 1 és a maradék 9 csúcs foka is azonos. Határozzuk meg a fa élkromatikus számát.
c) Egy 1000 csúcsú gráfot úgy kaptunk, hogy vettünk két 500 pontú utat, és az egyik út minden pontját összekötöttük a másik út minden pontjával. Mekkora az így kelektező gráfnak a kromatikus száma és az élkromatikus száma?
d) Egy 1001 csúcsú $G$ gráfot két körből, egy 500 pontú és egy 501 pontú körből készítünk úgy, hogy az egyik kör minden csúcsát összekötjük a másik kör minden csúcsával. Mekkora az így keletkező gráf kromatikus száma és élkromatikus száma?
Egy 1000 csúcsú teljes gráfból elhagyjuk egy Hamilton-kör éleit. Mekkora lesz az így kapott gráf kromatikus száma?
A $G$ gráf csúcshalmaza $V(G)=\{1,2,\dots,100\}$. Az $x,y \in V(G)$ csúcsok akkor legyenek szomszédosak $G$-ben, ha $x \neq y$ és $10 \mid x \cdot y$.
Határozzuk meg $G$ kromatikus számát.
Egy 8 csúcsú teljes gráfból töröljük egy 6 csúcsú kör éleit. Határozzuk meg a kapott gráf kromatikus számát.
Egy 100 csúcsú teljes gráfból töröljük egy 50 csúcsú kör éleit. Határozzuk meg a kapott gráf kromatikus számát.
A $G$ gráf csúcshalmaza $V(G)=\{1,2,\dots,1000\}$. Az $x,y \in V(G)$ csúcsok akkor legyenek szomszédosak $G$-ben, ha $x \neq y$ és $(x,y) \geq 10$. Határozzuk meg $G$ kromatikus számát.
Határozzuk meg egy 6 csúcsú kör komplementerének élkromatikus számát.
