The model-free string-graph coloring algorithm conjecture

Let GG be a string graph, let nn be its size, and let ω(G)\omega(G) and β(G)\beta(G) denote the parameters used by the source. An f(ω(G),β(G))f(\omega(G),\beta(G))-coloring is a coloring with the stated number of colors. Model-free string-graph coloring conjecture. There are functions f,C ⁣:N×NNf,C\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N} and an algorithm that takes a graph GG of size nn as input and, in nC(ω(G),β(G))n^{C(\omega(G),\beta(G))} time, either computes an f(ω(G),β(G))f(\omega(G),\beta(G))-coloring of GG or correctly reports that GG 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

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.