On bipartization of cubic graphs by removal of an independent set

We study a new problem for cubic graphs: bipartization of a cubic graph QQ by deleting sufficiently large independent set II. It can be expressed as follows: Given an integer  kkand a connected  nn-vertex tripartite cubic graph  Q=(V,E)Q=(V,E)with independence number  α(Q)α(Q), does  QQcontain an independent set  IIof size  kksuch that  Q−IQ−Iis bipartite?   We are interested for which values of kk the answer to this question is affirmative. We prove constructively that if α(Q)≥2n/5α(Q)≥2n/5, then the answer is positive for each kk satisfying ⌊(n−α(Q))/2⌋≤k≤α(Q)⌊(n−α(Q))/2⌋≤k≤α(Q). It remains an open question if a similar construction is possible for α(Q)<2n/5α(Q)<2n/5.We also show that this problem with α(Q)≥2n/5α(Q)≥2n/5 and kk satisfying ⌊n/3⌋≤k≤α(Q)⌊n/3⌋≤k≤α(Q) can be related to semi-equitable graph 3-coloring, where one color class is of size kk, and the subgraph induced by the remaining vertices is equitably 2-colored. This means that QQ has a coloring of type (k,⌈(n−k)/2⌉,⌊(n−k)/2⌋)(k,⌈(n−k)/2⌉,⌊(n−k)/2⌋).