Le's polynomial bound on induced paths in -free graphs
Let be a positive integer and let an -free graph be a graph containing no induced subgraph from the family . An induced path is a path whose vertices induce exactly the edges of the path.
Le's induced-path conjecture. There is a constant such that every -free -vertex graph has at most distinct induced paths.
This conjecture was raised earlier as an open question by Raymond. The paper places it in the context of recognizing -free graphs and does not report a resolution.
References
- Marthe Bonamy, Édouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé and Alexandra Wesolek, “Sparse graphs with bounded induced cycle packing number have logarithmic treewidth”, arXiv:2206.00594 (2024).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.