Pith. sign in

Long induced paths in $K_{s, s}$-free graphs

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

More than 40 years ago, Galvin, Rival and Sands showed that every $K_{s, s}$-free graph containing an $n$-vertex path must contain an induced path of length $f(n)$, where $f(n)\to \infty$ as $n\to \infty$. Recently, it was shown by Duron, Esperet and Raymond that one can take $f(n)=(\log \log n)^{1/5-o(1)}$. In this note, we give a short self-contained proof that a $K_{s, s}$-free graphs with an $n$-vertex path contains an induced path of length at least $(\log \log n)^{1-o(1)}$. Combined with the recent remarkable example of Cou\"etoux, Defrain, and Raymond, which provides an upper bound of $O((\log \log n)^{1+o(1)})$, this essentially resolves this old problem.

fields

math.CO 1

years

2025 1

verdicts

ACCEPT 1

representative citing papers

Graph classes through the lens of logic

math.CO · 2025-01-07 · accept · novelty 2.0

A survey presenting first-order transductions as a unifying lens for graph classes, connecting sparsity, twin-width, and monadic stability and dependence.

citing papers explorer

Showing 1 of 1 citing paper.

  • Graph classes through the lens of logic math.CO · 2025-01-07 · accept · none · ref 83 · internal anchor

    A survey presenting first-order transductions as a unifying lens for graph classes, connecting sparsity, twin-width, and monadic stability and dependence.