Polynomial-time MIS conjecture for graphs forbidding independent planar minors

From papers

Let HH be a planar graph and let kk be a positive integer. A graph is kHkH-free if it contains no kk pairwise non-adjacent independent HH-minor models. MIS denotes the Maximum Independent Set problem.

Independent-planar-minor MIS conjecture. For every planar HH and every kk, MIS is polynomial-time solvable on the class of kHkH-free graphs.

The paper proves an nO(logn)n^{O(\log n)}-time algorithm for this problem, so the conjecture asks whether the quasi-polynomial bound can always be improved to polynomial time. It remains open in the 2K32K_3-free case.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Maria Chudnovsky, Amadeus Reinald and Stéphan Thomassé, “Forbidding anticomplete planar minors: Induced Erdős–Pósa property and Maximum Independent Set in QP”, arXiv:2607.09646 (2026).

Solutions 0

No solutions have been posted yet.