For every integer t≥ 1 and every planar graph H, there exists a constant c=c(t,H) such that every graph G with no induced subgraph isomorphic to K_1,t and with no induced minor isomorphic to H satisfies operatornametree-alpha(G)≤ c. Here operatornametree-alpha(G)=min_(T,B_x)max_x∈ V(T)alpha(G[B_x]), where the minimum ranges over all tree decompositions (T,B_x) of G.

Dallard–Krnc–Kwon–Milanič–Munaro–Štorgel–Wiederrecht path-independence conjecture

The named conjecture concerns bounded tree-independence in graph classes excluding induced stars and planar graphs as induced minors. Retrieved sources do not explicitly formulate a separate path-independence conjecture.

Known results

Choi, Hilaire, Milanič, and Wiederrecht (June 10, 2025) proved the conjecture when the excluded planar graph is a $k$ -wheel, and gave polynomial-time algorithms for fixed parameters.
A December 2025 result established a polylogarithmic upper bound on tree-independence for $K_{1,s}$ -free, $H$ -induced-minor-free graphs.
A June 2026 paper proved the associated grid characterization for outerstring graphs and obtained bounds for other classes.
A July 2026 paper gave a broad sub-polynomial classification for induced-minor-closed classes, without settling the conjecture.

September 9, 2026 partial update

An indexed paper reports a broader bounded-path-independence regime and polynomial-time algorithms for related induced-minor problems, while explicitly describing the conjecture as only partially resolved. No complete proof, counterexample, or AI-attributed solution was found.

Current status (as of September 2026): Several substantial partial results and algorithmic consequences are known, but the general conjecture remains open.

Dallard–Krnc–Kwon–Milanič–Munaro–Štorgel–Wiederrecht path-independence conjecture

Primary source

Additional references

Progress summary

Solutions 0