W 1961 Erdos zapytał czy istnieje 4-kolorowanie liczb naturalnych, w którym
każde dwa sąsiednie segmenty są rozróżnialne poprzez multizbiór kolorów.
Odpowiedź jest pozytywna, ale znalezienie odpowiedniej konstrukcji wymagało
użycia komputera. Naturalna ciągła wersja problemu Erdosa brzmi następująco:
czy istnieje skończone mierzalne kolorowanie prostej rzeczywistej, w którym
dowolne dwa sąsiednie przedziały są rozróżnialne poprzez miarę Lebesgue'a?
To znaczy, miara pewnego koloru w jednym przedziale jest inna niż w drugim.
Okazuje się, że i w tym wypadku cztery kolory wystarczą, a prawdą jest nawet
więcej: dla dowolnego k istnieje 
-kolorowanie prostej, w którym żadnego
przedziału nie da się rozciąć w k miejscach, tak aby z otrzymanych
przedziałów dało się utworzyć dwie kolekcje o tej samej mierze każdego
koloru. Dowód jest niekonstruktywny i stosuje twierdzenie Baira o zbiorach
pierwszej kategorii.
Z drugiej strony, słynne twierdzenie o podziale
naszyjnika gwarantuje, że do takiego kolorowania potrzeba co najmniej 
kolorów. Dowód też jest niekonstruktywny i wykorzystuje twierdzenie
Borsuka-Ulama o antypodach. Czy te oszacowania pozostają prawdziwe dla
kolorowania liczb naturalnych - tego na razie nie wiadomo.