3-colorability conjecture for string graphs of sufficiently large odd girth
3-colorability conjecture for string graphs of sufficiently large odd girth
Let be an integer, and consider the class of string graphs whose odd girth is at least . String-graph coloring conjecture. There is an integer such that the class of string graphs of odd girth at least is 3-chromatic. While string graphs of large odd girth can contain arbitrarily large bipartite complete graphs and therefore are not -degenerate for any fixed , 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
Sign in to submit a solution.
No solutions have been posted yet.