Sparse graphs without long induced paths

DOI10.1016/J.JCTB.2023.12.003MaRDI QIDQ6196152zbMATH OpenOpenAlexFDO

Authors Oscar Defrain, Jean-Florent Raymond

Publication date 14 March 2024

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2304.09679

zbMATH Keywords

degeneracycoloring numberstypical induced subgraphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Abstract: Graphs of bounded degeneracy are known to contain induced paths of order $Omega(loglogn)$ when they contain a path of order $n$, as proved by Nev{s}etv{r}il and Ossona de Mendez (2012). In 2016 Esperet, Lemoine, and Maffray conjectured that this bound could be improved to $Omega((logn{)}^c)$ for some constant $c>0$ depending on the degeneracy. We disprove this conjecture by constructing, for arbitrarily large values of $n$, a graph that is 2-degenerate, has a path of order $n$, and where all induced paths have order $O((loglogn{)}^2)$. We also show that the graphs we construct have linearly bounded coloring numbers.

Recommendations

• Long induced paths in graphs
• Long induced paths in minor-closed graph classes and beyond
• Short proofs for long induced paths
• Going far from degeneracy
• Going far from degeneracy

Cites work

• A Ramsey-type theorem for traceable graphs
• Long induced paths in graphs
• Long induced paths in minor-closed graph classes and beyond
• Orderings on graphs and game coloring number
• Polynomial expansion and sublinear separators
• Sparsity. Graphs, structures, and algorithms

This page was built for publication: Sparse graphs without long induced paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6196152)