The model-free string-graph coloring algorithm conjecture

About 1 year old · traced to

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×N→Nf,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.

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

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.