Open problem on realizing every chromatic number by interval distance graphs

Let GDG_D be the distance graph on the plane whose vertices are the points of R2\mathbb{R}^2, with two points adjacent when their distance lies in DD. For b>1b>1, write G[1,b]G_{[1,b]} for the graph with distance set [1,b][1,b], and let χ\chi denote chromatic number.

Realization problem. For any integer k7k\ge 7, there exists b>1b>1 such that

χ(G[1,b])=k.\chi(G_{[1,b]})=k.

The problem asks whether interval distance graphs can realize every chromatic number at least 77. The paper notes that several values, including 88, 1010, and 1111, are not currently determined by the available constructions, so the question remains open.

Sources & referencesView supporting material

Primary source

Joanna Chybowska-Sokół, Konstanty Junosza-Szaniawski and Krzysztof Węsek, “Coloring distance graphs on the plane”, arXiv:2201.04499 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.