Le's polynomial bound on induced paths in -free graphs
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.
Sources & referencesView supporting material
Primary source
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.