Abstract
We study a new problem for cubic graphs: bipartization of a cubic graph by deleting sufficiently large independent set . It can be expressed as follows: \emph{Given a connected -vertex tripartite cubic graph with independence number , does contain an independent set of size such that is bipartite?} We are interested for which value of the answer to this question is affirmative. We prove constructively that if , then the answer is positive for each fulfilling . It remains an open question if a similar construction is possible for cubic graphs with . Next, we show that this problem with and fulfilling inequalities can be related to semi-equitable graph 3-coloring, where one color class is of size , and the subgraph induced by the remaining vertices is equitably 2-colored. This means that has a coloring of type .
Connections
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 review
No reviews yet.
Discussion 0
Add a comment
No comments yet.