On some optimization problems for star-free graphs

V. G. Naidenko, Yu. L. Orlovich

It is shown that in star-free graphs the maximum independent set problem, the minimum dominating set problem and the minimum independent dominating set problem are approximable up…