Bipartizando Grafos Livres de P6 pela Remoção de um Emparelhamento
Resumo
Dado um grafo G = (V,E), um emparelhamento bipartizante M de G é um emparelhamento cuja remoção elimina todos os ciclos ímpares de G (ou equivalentemente, se G − M é bipartido). Estudamos o problema de determinar se G admite um emparelhamento bipartizante. Este problema é equivalente ao de determinar se G admite uma (2, 1)-coloração, que é uma 2-coloração de V(G) tal que cada classe de cor induz um grafo de grau má́ximo igual a 1. Neste trabalho, estendemos o resultado de Lima et al. (2021) sobre grafos livres de P5, apresentando um algoritmo polinomial que decide se um grafo livre de P6 admite um emparelhamento bipartizante.
Palavras-chave:
Emparelhamentos, Grafos livres de P6, Deleçãoo de arestas, Algoritmos
Referências
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.
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.
Publicado
31/07/2022
Como Citar
LIMA, Carlos V. G. C.; MORAIS, Cícero S..
Bipartizando Grafos Livres de P6 pela Remoção de um Emparelhamento. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 141-144.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2022.223347.
