On bipartization of cubic graphs by removal of an independent set

preprint2014arXivOpen access

Abstract

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: \emph{Given a connected nn-vertex tripartite cubic graph Q=(V,E)Q=(V,E) with independence number α(Q)α(Q), does QQ contain an independent set II of size kk such that Q−IQ-I is bipartite?} We are interested for which value of kk the answer to this question is affirmative. We prove constructively that if α(Q)≥4n/10α(Q) \geq 4n/10, then the answer is positive for each kk fulfilling ⌊(n−α(Q))/2⌋≤k≤α(Q)\lfloor (n-α(Q))/2 \rfloor \leq k \leq α(Q). It remains an open question if a similar construction is possible for cubic graphs with α(Q)<4n/10α(Q)<4n/10. Next, we show that this problem with α(Q)≥4n/10α(Q)\geq 4n/10 and kk fulfilling inequalities ⌊n/3⌋≤k≤α(Q)\lfloor n/3 \rfloor \leq k \leq α(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, \lceil(n-k)/2\rceil, \lfloor (n-k)/2 \rfloor).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.