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

2. gyakorlat, 2005. február 25.

                                       Koblinger Egmont <egmont@cs.bme.hu>

Gráfok színezése

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

16. 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?

17. Minden páros G gráfra χ(G) ⩽ 2. Mikor nem áll egyenlőség?

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

19. Legfeljebb hány éle lehet egy n csúcsú páros gráfnak?

20. Mennyi a Petersen-gráf kromatikus száma?

21. Legyen V (G) = {v_{1}, …, v_{106}}, v_{i} és v_{j} között pontosan akkor van él, ha |i − j| ⩽ 7. Mennyi G kromatikus száma?

22. Egy gráf pontjait a sakktáblai mezői alkotják. Pontosan akkor megy él két mező között, ha az egyik mezőről a másikra bástyával át tudunk lépni. Hány színnel színezhető ez a gráf?

23. 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?

24. 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.

25. Hagyjuk el egy 2n pontú teljes gráfból egy Hamilton-körének az éleit. Mennyi a keletkező gráf kromatikus száma? Mi a helyzet akkor, ha egy 2n + 1 csúcsú teljes gráfból indulunk ki?

26. Legyen G és H két különböző gráf (diszjunkt ponthalmazokkal). Készítsünk belőlük egyetlen F gráfot úgy, hogy G minden pontját összekötjük H minden pontjával. Bizonyítsuk be, hogy χ(F) = χ(G) + χ(H).

27. Legyen G_{1} és G_{2} két gráf ugyanazon V csúcshalmazon és jelölje G a G_{1} ∪ G_{2} = (V, E(G_{1} ∪ G_{2})) módon megadható gráfot. Mutassuk meg, hogy χ(G) ⩽ χ(G_{1})χ(G_{2}).

28. Legyen G olyan hurokmentes gráf, amelynek pontosan \binom{χ(G)}{2} éle van. Bizonyítandó, hogy G-ben a nem izolált pontok egy K_{χ(G)}-t alkotnak.

29. Adott a síkon egyenesek egy halmaza, melyek közül semelyik három nem megy át egy ponton.

(a) Legyenek a G_{1} gráf csúcsai az egyenesek metszéspontjai – két csúcs pontosan akkor szomszédos G_{1}- ben, ha a megfelelő metszéspontok valamelyik egyenesen szomszédosak. Igazoljuk, hogy χ(G_{1}) ⩽ 3.

(b) Legyenek a G_{2} gráf csúcsai az egyenesek által létrehozott tartományok – két csúcs pontosan akkor szomszédos G_{2}-ben, ha a megfelelő tartományoknak van közös határszakaszuk. Igazoljuk, hogy χ(G_{2}) ⩽ 2.

30. Bizonyítsuk be, hogy minden gráfnak sorbarendezhetők úgy a csúcsai, hogy ha ebben a sorrendben színezzük a gráfot mohó algoritmussal, akkor χ(G) színt használunk.

31. Lássuk be, hogy |E(G)| ≥ \binom{χ(G)}{2}.