Feladat: A.657 Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 2015/december, 540. oldal  PDF  |  MathML 
Témakör(ök): Nehéz feladat, Gráfelmélet, Kettes alapú számrendszer, Számelmélet

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Legyen {xn} a van der Korput sorozat, azaz ha a pozitív egész n bináris alakja n=iai2i (ai{0,1}), akkor xn=iai2-i-1. Legyen V a síkbeli (n,xn) pontok halmaza, ahol n pozitív egész. Legyen G az a gráf, melynek csúcshalmaza V, és amelyben két különböző csúcsot, p-t és q-t akkor és csak akkor kötjük össze éllel, ha van olyan ‐ a koordinátatengelyekkel párhuzamos állású ‐ R téglalap, melyre RV={p,q}. Igazoljuk, hogy G kromatikus száma véges.