Sparse graphs without long induced paths

DOI10.1016/J.JCTB.2023.12.003arXiv2304.09679OpenAlexW4366464678MaRDI QIDQ6196152FDOQ6196152

Authors: Oscar Defrain, Jean-Florent Raymond 

Publication date: 14 March 2024

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

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.

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

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

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)

Cites Work

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

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)