On bipartization of cubic graphs by removal of an independent set

DOI10.1016/J.DAM.2015.10.036MaRDI QIDQ298966zbMATH OpenOpenAlexFDO

Authors Hanna Furmańczyk, Marek Kubale, Stanisław P. Radziszowski

Publication date 21 June 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.2728

zbMATH Keywords

bipartizationcubic graphsdecycling numberequitable coloringfeedback-vertex setindependent set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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)geq4n/10$, then the answer is positive for each $k$ fulfilling $lfloor(n-alpha(Q))/2floorleqkleqalpha(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)geq4n/10$ and $k$ fulfilling inequalities $lfloorn/3floorleqkleqalpha(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)/2ceil,lfloor(n-k)/2floor)$.

Recommendations

• Packing and covering odd cycles in cubic plane graphs with small faces
• Packing and covering odd cycles in cubic plane graphs with small faces
• On a bipartition problem of Bollobás and Scott
• Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
• Independent domination in bipartite cubic graphs

Cites work

• Algorithm Engineering for Optimal Graph Bipartization
• Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
• Equitable coloring and the maximum degree
• Fast algorithms for max independent set
• Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
• Graph Bipartization and via minimization
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Independent sets in triangle-free cubic planar graphs
• Maximum independent sets in 3- and 4-regular Hamiltonian graphs
• On the independence number of random cubic graphs
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three

Cited in

(2)

• On the computational complexity of the bipartizing matching problem
• Graph modification of bounded size to minor-closed classes as fast as vertex deletion

This page was built for publication: On bipartization of cubic graphs by removal of an independent set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q298966)