Bipartizando Grafos Livres de P6 pela Remoção de um Emparelhamento - Lima, Carlos V. G. C.; Morais, Cícero S. (Anais do Encontro de Teoria da Computação (ETC); 2022: Anais do VII Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2022.223347, 2022)
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 P 5 , apresentando um algoritmo polinomial que decide se um grafo livre de P 6 admite um emparelhamento bipartizante.