Feladat: 1.13.
Tekintsük azt a gráfot, amelynek csúcsai egy
8×8 sakktábla mezői, és kössünk össze két csúcsot, ha a megfelelő mezőknek
a) van közös éle,
b) van közös csúcsa.
Mennyi az így kapott gráfok kromatikus száma?
Megoldás: 1.13
a) A sakktábla szokásos színezése bizonyítja, hogy ez a gráf két színnel színezhető (páros) gráf.
b) A sakktábla bal alsó sarkában álló négy mező (A1, A2, B1, B2) mindegyikét él köti össze mindegyikkel, tehát a színezéshez legalább négy szín kell.
Négy szín elég is a színezéshez. Ha két nem szomszédos sor mezői közül semelyiket semelyikkel nem köt össze él, tehát ha minden második sorban meghagyjuk a szokásos színezést, viszont a többiben a feketét kékre, a fehéret zöldre változtatjuk, akkor a gráf egy megfelelő színezését kapjuk.