Le's polynomial bound on induced paths in O2\mathcal{O}_2-free graphs

Let nn be a positive integer and let an O2\mathcal{O}_2-free graph be a graph containing no induced subgraph from the family O2\mathcal{O}_2. An induced path is a path whose vertices induce exactly the edges of the path.

Le's induced-path conjecture. There is a constant cc such that every O2\mathcal{O}_2-free nn-vertex graph has at most ncn^c distinct induced paths.

This conjecture was raised earlier as an open question by Raymond. The paper places it in the context of recognizing Ok\mathcal{O}_k-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

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.