Bevezetés a számításelméletbe II.

2. gyakorlat, 2007. február 21.

                                      Koblinger Egmont <egmont@cs.bme.hu>

Gráfszínezések 1.

16. Bizonyítsuk be, hogy ha egy páros gráf minden csúcsának fokszáma 4, akkor van benne olyan kör, melynek hossza legalább 8.

17. Hány szín szükséges az alábbi gráf pontjainak kiszínezéséhez?

18. Legyen V (G) = {v_{1}, …, v_{100}}, ahol v_{i} és v_{j} között akkor és csak akkor megy él, ha 7 ≥ |i − j|. Mennyi G kromatikus száma?

19. Legyenek G csúcsai az összes természetes számok és legyen az n és m csúcs éllel összekötve pontosan akkor, ha n + m páratlan. Mennyi a gráf kromatikus száma?

20. A V (G) = 1, 2, … 1023 ponthalmazon definiáljuk a G gráfot úgy, hogy benne k és m pontosan akkor van összekötve éllel, ha nem egyenlőek és az egyik osztja a másikat. Határozzuk meg χ(G) értékét.

21. Bizonyítsuk be, hogy minden n csúcsú gráfra χ(G) · χ(\overline{G}) ⩾ n.

22. Bizonyítsuk be, hogy minden páros G gráfra χ(G) = ω(G).

23. Bizonyítsuk be, hogy tetszőleges egyszerű gráfra |E(G)| ≥ \binom{χ(G)}{2}.

24. Igaz-e, hogy minden egyszerű G gráfnak van olyan χ(G) színnel való színezése, melyben az egyik színosztály α(G) csúcsot tartalmaz? (α: független pontok maximális száma.)

25. Mutassuk meg, hogy ha G_{1} és G_{2} két gráf ugyanazon a V csúcshalmazon, G pedig a szintén ezen a csúcshalmazon definiált, G_{1} és G_{2} éleinek unióját tartalmazó gráf, akkor χ(G) ≤ χ(G_{1})χ(G_{2}).

26. Legyen adva a síkon véges sok egyenes, melyek közül semelyik három sem metszi egymást egy pontban. Legyenek a G gráf csúcsai a metszéspontok, élei pedig az egyes egyeneseken a szomszédos csúcspárok közötti szakaszok. Bizonyítandó, hogy χ(G) ≤ 3.