Feladat: 1.15.
([
4] 66. old.)
Egy gráf pontjai az
1,2,…,100 számok, két számot akkor köt össze él, ha közülük a nagyobbikat a kisebbikkel osztva kettőhatványt kapunk. Mennyi ennek a gráfnak a kromatikus száma?
Megoldás: 1.15
Írjunk fel minden
a számot
a=
2k
b alakban, ahol
b páratlan. Ez a felírás egyértelmű. Színezzük
a-t ezután a
k-adik színnel. Ha
b is ugyanezt a színt kapta, akkor hányadosuk különbözik 1-től és két páratlan szám hányadosa, tehát nem kettőhatvány. Ez tehát a gráf egy jólszínezése 7 színnel. Másrészt az
1,2,4,8,16,32,64 számok közül bármely kettő össze van kötve éllel, tehát
K7
-et alkot a gráfban, így hétnél kevesebb színnel nem is színezhető a gráf.