1 vote

Maximal classes for which largest independent set can be found in polynomial time?

In the meantime, it was shown that the problem is polynomial-time solvable on $P_6$-free graphs: Andrzej Grzesik, Tereza Klimosov√°, Marcin Pilipczuk, Michal Pilipczuk: Polynomial-time Algorithm for ...
Christian Komusiewicz's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible