Polynomial algorithm for finding the largest independent sets in graphs without forks ?
A fork is a graph that is obtained from K1,3 by subdividing one edge. It is known [6], [7]and[8] that for K1,3-free graphs the problem of finding the largest independent set can be solved in a polynomial time. In this paper, we prove that this is also true for the wider class of fork-free graphs.
polynomial algorithm graph independent set of vertices claw-free graphs