← All problems

Linear coloring conjecture for touching sets of strings

11 years old · traced to

A touching set of strings is a finite family of strings in the plane in which no pair crosses, and it is kk-touching if every point of the plane belongs to at most kk strings. Linear coloring conjecture. There is a constant c>0c>0 such that every kk-touching set of strings can be colored with ckck colors. The conjecture was subsequently proved by Fox and Pach, who obtained the bound 6ek+16ek+1 colors.

References

Status

  • Solved: Louis Esperet, Daniel Gonçalves, and Arnaud Labourel. Coloring Non-Crossing Strings (The Electronic Journal of Combinatorics, 2016) https://doi.org/10.37236/5710

Source: Louis Esperet, Daniel Gonçalves and Arnaud Labourel, “Coloring non-crossing strings”, arXiv:1511.03827 (2016).

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.