Long induced paths in expanders

DOI10.1017/S096354832400035XMaRDI QIDQ6880005zbMATH OpenFDO

Authors Nemanja Draganić, Peter Keevash

Publication date 29 December 2025

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1017/S096354832400035X

zbMATH Keywords

DFS algorithmexpansioninduced pathsinduced size-Ramsey numberspseudorandom graphsRamsey theoryupper uniform

Mathematics Subject Classification ID

Paths and cycles (05C38) Expander graphs (05C48) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Cites work

• Algorithms for maximum weight induced paths
• An upper bound on the size of the snake-in-the-box
• Cliques in random graphs
• Combinatorial Gray codes -- an updated survey
• Effective bounds for induced size-Ramsey numbers of cycles
• Expander graphs and their applications
• scientific article; zbMATH DE number 434900 (Why is no real title available?)
• scientific article; zbMATH DE number 3999982 (Why is no real title available?)
• scientific article; zbMATH DE number 932179 (Why is no real title available?)
• Induced trees in sparse random graphs
• Large induced matchings in random graphs
• Large induced trees in sparse random graphs
• Maximal induces trees in sparse random graphs
• New lower bounds on the size-Ramsey number of a path
• On colouring random graphs
• On large induced trees and long induced paths in sparse random graphs
• On size Ramsey number of paths, trees, and circuits. I
• On some multicolor Ramsey properties of random graphs
• On the independence number of random graphs
• On the snake in the box problem
• Recent developments in graph Ramsey theory
• Short proofs for long induced paths
• Sparse graphs without long induced paths
• Sparsity. Graphs, structures, and algorithms
• The Induced Size-Ramsey Number of Cycles
• The largest hole in sparse random graphs
• The size of the largest hole in a random graph
• Trees in random graphs

Cited in

(1)

• Combinatorics. Abstracts from the workshop held January 4--9, 2026

This page was built for publication: Long induced paths in expanders

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