The struction of a graph: Application to CN-free graphs (Q1068855)

A graph is CN-free if it contains neither C, the claw, nor N, the net (unique graphs with degree sequences \((3,1,1,1)\) and \((3,3,3,1,1,1),\) respectively) as subgraphs. For the class of CN-free graphs, a polynomial time algorithm is described for determining the stability number a(G). The basic idea of the algorithm consists in a reduction procedure (called here struction) associating to any CN-free graph G another such a graph G' with \(a(G')=a(G)-1\).