Polynomial-time MIS conjecture for graphs forbidding independent planar minors

Less than 1 year old · traced to

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(log⁡n)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.

References

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).

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.