Egy hires problema a kombinatorikaban az "egysegtavolsag graf kromatikus szama". 

 A kovetkezorol van szo:

  Egy szep elemi faladat, hogyha a sik pontjait akarhogy kiszinezzuk harom szinnel, akkor lesz ket olyan pont, melyek szine azonos, es melyek tavolsaga pontosan 1.

 Hasonlo elemi feladat, hogy pl 9 (sot akar 7) szinnel mar ki lehet szinezni  a sikot ugy, hogy ket azonos szinu pont tavolsaga soha sem lesz 1.

  Ebbol az kovetkezik, hogy a 4, 5, 6, 7 szamok kozott van egy olyan, hogy annyi szinnel meg ki lehet szinezni a sikot ugy, hogy ne legyenek azonos szinu pontok 1 tavolsagra, de kevesebbel mar nem.

 Kerdes, hogy pontosan melyik ez a szam?

 Sot, az is erdekes lenne, ha valaki ki tudna zarni a fenti lehetosegek barmelyiket.

 

 Egy erdekes velemeny amit ezzel kapcsolatban olvastam, hogy ez akar fugghet

 attol is, hogy elfogadjuk e a kivalasztasi axiomat vagy nem

(pl Soifer es Shelah nevere erdemes rakeresni).

 

Erdos es De Brujin egy klasszikus tetele szerint ha egy adott szinre nincs megfelelo szinezes, akkor van egy olyan veges reszhalmaza a siknak, hogy mar az sem szinezheto jol.