





















In 2012, Nešetřil and Ossona de Mendez proved that graphs of bounded degeneracy that have a path of order $n$ also have an induced path of order $Ω(\log \log n)$. In this paper we give an almost matching upper bound by describing, for arbitrarily large values of $n$, 2-degenerate graphs that have a path of order $n$ and where the longest induced paths have order $O((\log \log n)^{1+o(1)})$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。