The model-free string-graph coloring algorithm conjecture
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.