Open problem on realizing every chromatic number by interval distance graphs
Open problem on realizing every chromatic number by interval distance graphs
Let be the distance graph on the plane whose vertices are the points of , with two points adjacent when their distance lies in . For , write for the graph with distance set , and let denote chromatic number.
Realization problem. For any integer , there exists such that
The problem asks whether interval distance graphs can realize every chromatic number at least . The paper notes that several values, including , , and , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.