Linear K_{r-1}-free subgraph in K_r-free segment graphs
Problem 1.2 · arXiv:2112.02378
Status open high confidence
Problem 1.2 asks whether every K_r-free segment graph on n vertices contains an induced K_{r-1}-free subgraph on \Omega_r(n) vertices. The source paper (Fox–Pach–Suk 2022) establishes analogous results for string graphs with a log^2(n) factor loss (Theorems 1.5–1.6), but the segment-graph case with a linear guarantee remains explicitly unresolved. A wide search of the post-2022 literature found no paper resolving the segment-graph case; the conjecture is open with high confidence.
Reviewer notes. The closest post-2022 work found is arXiv:2409.06650 ('Induced Subgraphs of K_r-Free Graphs and the Erdős–Rogers Problem', Combinatorica 2025), which studies the Erdős–Rogers problem for general (non-geometric) K_r-free graphs; it does not address segment graphs and does not cite 2112.02378. No paper specifically resolving Problem 1.2 for segment graphs was found in the indexed literature.
Context
Motivated by the approach of coloring $K_r$-free string graphs to prove Conjecture 1.1: if each color class could be made $K_4$-free, Ackerman's result would bound the edges per class by $O(n)$. Although Krawczyk–Walczak showed $K_r$-free string graphs can require $\Omega_r(\log\log n)$ colors with $K_{r-1}$-free classes, the question of finding a linearly large $K_{r-1}$-free induced subgraph in a $K_r$-free segment graph remains open. The paper's Theorems 1.5 and 1.6 address analogous questions for string graphs (with a $\log^2 n$ loss), but the segment-graph case with a linear guarantee is unresolved.
Source paper
Quasiplanar Graphs, String Graphs, and the Erdos-Gallai Problem
Jacob Fox, Janos Pach, Andrew Suk · 2022-10-25
https://arxiv.org/abs/2112.02378
PDF source