Bipartizing P6-Free Graphs by Removing a Matching

• Carlos V. G. C. Lima UFCA
• Cícero S. Morais UFCA

DOI: https://doi.org/10.5753/etc.2022.223347

Abstract

Given a graph G = (V,E), a bipartizing matching M of G is a matching whose removal eliminates all the odd cycles of G (or equivalently, whether G−M is bipartite). We study the problem of determining whether G admits a bipartizing matching. This problem is equivalent to determine whether G admits a (2, 1)-coloring, which is a 2-coloring of V(G) such that each color class induces a graph of maximum degree at most 1. In this paper, we extend the result of Lima et al. (2021) about P₅-free graphs by showing a polynomial-time algorithm that decides whether a P₆-free graph admits a bipartizing matching.

Keywords: Matchings, P6-free Graphs, Edge deletion, Algorithms

References

Alon, N. and Stav, U. (2009). Hardness of edge-modification problems. Theoretical Computer Science, 410(47–49):4920 – 4927.

Bondy, J. A. and Murty, U. S. R. (2008). Graph theory, volume 244 of Graduate Texts in Mathematics. Springer-Verlag London.

Borodin, O., Kostochka, A., and Yancey, M. (2013). On 1-improper 2-coloring of sparse graphs. Discrete Mathematics, 313(22):2638–2649.

Burzyn, P., Bonomo, F., and Durán, G. (2006). Np-completeness results for edge modification problems. Discrete Applied Mathematics, 154(13):1824–1844.

Camby, E. and Schaudt, O. (2016). A new characterization of Pk-free graphs. Algorithmica, 75(1):205–217.

Furmánczyk, H., Kubale, M., and Radziszowski, S. (2015). On bipartization of cubic graphs by removal of an independent set. Discrete Applied Mathematics. In Press, Corrected Proof.

Guillemot, S., Havet, F., Paul, C., and Perez, A. (2012). On the (non-)existence of polynomial kernels for p-free edge modification problems. Algorithmica, 65(4):900–926.

Lima, C., Rautenbach, D., Souza, U., and Szwarcfiter, J. (2021). On the computational complexity of the bipartizing matching problem. In Press.

Lima, C. V., Rautenbach, D., Souza, U. S., and Szwarcfiter, J. L. (2017). Decycling with a matching. Information Processing Letters, 124:26–29.

Natanzon, A., Shamir, R., and Sharan, R. (2001). Complexity classification of some edge modification problems. Discrete Applied Mathematics, 113(1):109–128. Selected Papers: 12th Workshop on Graph-Theoretic Concepts in Computer Science.

Protti, F. and Souza, U. S. (2018). Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs. Discrete Mathematics & Theoretical Computer Science, vol. 20 no. 2.

van ’t Hof, P. and Paulusma, D. (2010). A new characterization of p6-free graphs. Discrete Applied Mathematics, 158(7):731–740. Third Workshop on Graph Classes, Optimization, and Width Parameters Eugene, Oregon, USA, October 2007.

Yannakakis, M. (1981). Edge-deletion problems. SIAM Journal on Computing, 10(2):297–309.