Feladat:
Állapítsuk meg az alábbi gráfok kromatikus számát:
Feladat:
Állapítsuk meg az alábbi gráfok kromatikus számát:
Feladat:
Legyen H az ábrán látható gráf.
Határozzuk meg H kromatikus számát.
Otthoni munkára javasolt feladat: Határozzuk meg az összes olyan gráf kormatius számát, amelyet H-ból egy él elhagyásával nyerünk
Feladat: Színezzük ki a sakktábla mezőit úgy, hogy (i) a király (ii) a bástya (iii) a futó (iv) a huszár minden lépésénél az elfogalat mezót tekintve színváltás történjen.
Feladat: A síkon egyeneseket rajzolunk úgy, hogy semelyik három sem halad át egy ponton. A metszéspontok közül kettő szomszédos, ha egy egyenesre esnek, de nincs koz;öttük más metszéspont. Bizonyítsuk be, hogy a metszés pontok kiszínezhetők 3 színnel úgy, hogy a szomszédosak különböző színeket kapjanak.
Feladat: A síkon azonos állású egység négyzetek vannak elhelyezve úgy, hogy a sík mindegyik pontját maximum kettő négyzet fedi le. Bizonyítsuk be, hogy a négyzetek kiszínezhetők három színnel úgy, hogy közös ponttal rendelkező négyzetek különböző színt kapjanak.
Feladat: Hány jó 2-színezése van egy páros gráfnak?
Feladat: Hány jó 3 színezése van egy n pontú fának?
Feladat: Egy G gráf csúcshalmazát két diszjunkt nem-üres (S és T) részre osztjuk. Bizonyítsuk be, hogy
khi(G) <= khi(G|S)+khi(G|T).
Tegyük fel, hogy S egy maximális (nem bővíthető) klikk, amely nem az egész gráf (azaz T nem-üres). Ekkor
khi(G) <= khi(G|S)+khi(G|T)-1.