On bipartization of cubic graphs by removal of an independent set

Abstract

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: \emph{Given a connected $n$-vertex tripartite cubic graph $Q=(V,E)$ with independence number $\alpha (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 $\alpha (Q)\ge 4n/10$, then the answer is positive for each $k$ fulfilling $\lfloor (n-\alpha (Q))/2\rfloor \le k\le \alpha (Q)$. It remains an open question if a similar construction is possible for cubic graphs with $\alpha (Q)<4n/10$. Next, we show that this problem with $\alpha (Q)\ge 4n/10$ and $k$ fulfilling inequalities $\lfloor n/3\rfloor \le k\le \alpha (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,\lceil (n-k)/2\rceil ,\lfloor (n-k)/2\rfloor )$.

Cited by in corpus (1)

• Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines