On bipartization of cubic graphs by removal of an independent set

We study a new problem for cubic graphs: bipartization of a cubic graph Q by deleting sufficiently large independent set I. It can be expressed as follows: Given a connected n-vertex tripartite cubic graph Q = (V, E) with independence number α(Q), does Q contain an independent set I of size k such that Q − I is bipartite? We are interested for which value of k the answer to this question is affirmative. We prove constructively that if α(Q) ≥ 4n/10, then the answer is positive for each k fulfilling ⌊(n − α(Q))/2⌋ ≤ k ≤ α(Q). It remains an open question if a similar construction is possible for cubic graphs with α(Q) \u3c 4n/10. Next, we show that this problem with α(Q) ≥ 4n/10 and k fulfilling inequalities ⌊n/3⌋ ≤ k ≤ α(Q) can be related to semi-equitable graph 3-coloring, where one color class is of size k, and the subgraph induced by the remaining vertices is equitably 2-colored. This means that Q has a coloring of type (k, ⌈(n − k)/2⌉, ⌊(n − k)/2⌋)