The Maximum Independent Set Problem in Subclasses of Subcubic Graphs

The Maximum Independent Set problem is NP-hard and remains NP-hard for graphs of maximum degree at most three (also called subcubic graphs). In this paper, we will study its complexity in subclasses of subcubic graphs.Let Si,j,kSi,j,k be the graph consisting of three induced paths of lengths i,ji,j and kk, with a common initial vertex and Aql be the graph consisting of an induced cycle CqCq (q≥3q≥3) and an induced path with ll edges having an end-vertex in common with the CqCq. For example S0,0,lS0,0,l and A41 are known as path of length ll and banner, respectively.Our main result is that the Maximum Independent Set problem can be solved in polynomial time in the class of subcubic, (S2,j,k,A5l)-free graphs.