Bounds on independent isolation in graphs

An isolating set of a graph is a set of vertices S such that, if S and its neighborhood is removed, only isolated vertices remain; and the isolation number is the minimum size of such a set. It is known that for every connected graph apart from K 2 and C 5 , the isolation number is at most one-third the order and indeed such a graph has three disjoint isolating sets. In this paper we consider isolating sets where S is required to be an independent set and call the minimum size thereof the independent isolation number. While for general graphs of order n the independent isolation number can be arbitrarily close to n / 2 , we show that in bipartite graphs the vertex set can be partitioned into three disjoint independent isolating sets, whence the independent isolation number is at most n / 3 ; while for 3-colorable graphs the maximum value of the independent isolation number is ( n + 1 ) / 3 . We also provide a bound for k -colorable graphs.