The model-free string-graph coloring algorithm conjecture
Let be a string graph, let be its size, and let and denote the parameters used by the source. An -coloring is a coloring with the stated number of colors. Model-free string-graph coloring conjecture. There are functions and an algorithm that takes a graph of size as input and, in time, either computes an -coloring of or correctly reports that is not a string graph. The source previously describes this algorithm when an intersection model is supplied; removing that requirement is left as an open conjecture.
References
Primary source
Tara Abrishami, Marcin Briański, James Davies, Xiying Du, Jana Masaříková, Paweł Rzążewski and Bartosz Walczak, “Burling graphs in graphs with large chromatic number”, arXiv:2510.19650 (2025).
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
No solutions have been posted yet.