The linear induced-subgraph conjecture for circle graphs
The linear induced-subgraph conjecture for circle graphs
A circle graph is the intersection graph of chords of a circle. Let and be positive integers, and let the circle graph have vertices. The linear induced-subgraph conjecture. Every -free circle graph on vertices contains an induced subgraph on vertices which is -free. This would improve the currently described bound of , obtained from known chromatic-number estimates for circle graphs. Whether the linear bound holds is left open.
Sources & referencesView supporting material
Primary source
Jacob Fox, Janos Pach and Andrew Suk, “Quasiplanar Graphs, String Graphs, and the Erdos-Gallai Problem”, arXiv:2112.02378 (2022).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.