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

About 2 years old · traced to

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.

References

Primary source

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

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.