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

6. gyakorlat, 2006. március 27.

                                Koblinger Egmont <egmont@cs.bme.hu>

Színezések 2. – Perfekt gráfok

57. 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}).

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

59. Mennyi a Petersen-gráf élkromatikus száma?

60. Határozzuk meg K_{n} élkromatikus számát. Mutassunk is egy jó élszínezést.

61. n csapat körmérkőzést szeretne játszani (mindegyik csapat mindegyikkel egy meccset). Legalább hány forduló szükséges ennek lebonyolításához? (Egy fordulóban több pályán is folyhat párhuzamosan mérkőzés.)

62. Mennyi az élkromatikus száma egy r-reguláris páros gráfnak?

63. Bizonyítsuk be, hogy az összehasonlítási gráf perfekt.

64. Bizonyítsuk be, hogy egy intervallumgráf komplementere összehasonlítási gráf.

65. Mutassunk olyan nem perfekt gráfot, amelyre χ(G) = ω(G).

66. Legyenek egy gráf csúcsai a számok 1-től n-ig, és két (különböző) csúcs akkor legyen összekötve, ha ez egyik osztója a másiknak. Bizonyítsuk be, hogy az így kapott gráf minden n-re perfekt!

67. Adott a síkon néhány körvonal, ezekhez rendeljük a következő G gráfot. G csúcsai feleljenek meg egy-egy adott körvonalnak, és kettő akkor legyen összekötve, ha a két megfelelő körvonal egyike teljesen a másik belsejében halad. Bizonyítsuk be, hogy az így megadott G gráf perfekt.