The induced-path conjecture for the graphs Gq,pG_{q,p}

Let q3q\geq 3 be odd, let p1p\geq 1, and let Gq,pG_{q,p} be the graph constructed in the paper. Here, PtP_t denotes the path on tt vertices, and a graph is PtP_t-free if it has no induced subgraph isomorphic to PtP_t. Induced-path conjecture. For every p1p\geq 1, the graph Gq,pG_{q,p} is P3q2P_{3q-2}-free. This would improve the general bound from Theorem~; the case q=3q=3 is supported by the known P7P_7-freeness of G3,pG_{3,p}, while the conjecture remains open for the other cases discussed here.

Sources & referencesView supporting material

Primary source

Jan Goedgebeur, Jorik Jooken, Karolina Okrasa, Paweł Rzążewski and Oliver Schaudt, “Minimal obstructions to C_5-coloring in hereditary graph classes”, arXiv:2404.11704 (2026).

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.