Stability in CAN-free graphs (Q762505): Difference between revisions

A CAN-free graph is defined to be a graph not containing subgraphs isomorphic to \(K_{1,3}\), the graph with degree sequence (1,2,2,3,3,3) which does not contain \(K_{1,3}\), or the graph with degree sequence (1,1,1,3,3,3). Every CAN-free graph G can be associated with another such graph G' with fewer nodes and having stability number exactly one less than that of G. This gives an efficient algorithm for determining the stability number of CAN-free graphs.