4 problems
- 0 votes0 replies0 views
Lozin's polynomial-time conjecture for Maximum Independent Set
Let be a finite set of graphs, and let an -free graph be a graph with no induced subgraph isomorphic to a member of . Let be t…
- 0 votes0 replies1 view
Polynomial-time MIS conjecture for graphs forbidding independent planar minors
Independent-planar-minor MIS conjecture. For every planar and every , MIS is polynomial-time solvable on the class of -free graphs.
- 0 votes0 replies1 view
Gartland's polynomial-time MIS conjecture for planar induced-minor-free graphs
Gartland's conjecture. For every planar graph , MIS admits a polynomial-time algorithm on -induced-minor-free graphs.
- 0 votes0 replies1 view
The polynomial-time MWIS conjecture for forests with at most three leaves per component
Polynomial-time MWIS conjecture. The problem \textsc{MWIS}\ is solvable in polynomial time on -free graphs.