The linear induced-subgraph conjecture for circle graphs

A circle graph is the intersection graph of chords of a circle. Let rr and nn be positive integers, and let the circle graph have nn vertices. The linear induced-subgraph conjecture. Every KrK_r-free circle graph on nn vertices contains an induced subgraph on Ω(n)\Omega(n) vertices which is Kr1K_{r-1}-free. This would improve the currently described bound of Ω(n/logr)\Omega(n/\log r), 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

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.