3-colorability conjecture for string graphs of sufficiently large odd girth

From papers

Let kk be an integer, and consider the class of string graphs whose odd girth is at least kk. String-graph coloring conjecture. There is an integer kk such that the class of string graphs of odd girth at least kk is 3-chromatic. While string graphs of large odd girth can contain arbitrarily large bipartite complete graphs and therefore are not dd-degenerate for any fixed dd, the source gives no known proof or disproof of this 3-colorability assertion.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Édouard Bonnet and Paweł Rzążewski, “An 11/6-Approximation Algorithm for Vertex Cover on String Graphs”, arXiv:2409.18820 (2024).

Solutions 0

No solutions have been posted yet.