On bipartization of cubic graphs by removal of an independent set

DOI10.1016/j.dam.2015.10.036zbMath1339.05285arXiv1406.2728OpenAlexW2177022054MaRDI QIDQ298966

Hanna Furmańczyk, Marek Kubale, Stanislaw 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

independent setcubic graphsequitable coloringbipartizationdecycling numberfeedback-vertex set

Mathematics Subject Classification ID

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

Related Items

On the computational complexity of the bipartizing matching problem

Cites Work

• Unnamed Item
• Maximum independent sets in 3- and 4-regular Hamiltonian graphs
• Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• Equitable coloring and the maximum degree
• Fast algorithms for max independent set
• Independent sets in triangle-free cubic planar graphs
• Algorithm Engineering for Optimal Graph Bipartization
• Graph Bipartization and via minimization
• On the independence number of random cubic graphs
• Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling