Stable sets in {ISK4,wheel}-free graphs
arXiv:1602.02916 · doi:10.1007/s00453-016-0255-3
Abstract
An ISK4 in a graph G is an induced subgraph of G that is isomorphic to a subdivision of K4 (the complete graph on four vertices). A wheel is a graph that consists of a chordless cycle, together with a vertex that has at least three neighbors in the cycle. A graph is {ISK4,wheel}-free if it has no ISK4 and does not contain a wheel as an induced subgraph. We give an O(|V(G)|^7)-time algorithm to compute the maximum weight of a stable set in an input weighted {ISK4,wheel}-free graph G with non-negative integer weights.