Frustração de Arestas em (3, 6)-Fullerenes - Nicodemos, Diego S.; Klein, Sulamita; Faria, Luerbio (Anais do Encontro de Teoria da Computação (ETC); 2016: Anais do I Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2016.9765, 2016)
Grafos (3, 6)-fullerenes são grafos planares, 3-conexos, cúbicos cujas faces têm tamanho 3 ou 6. Determinar o menor número de arestas a serem deletadas de um grafo de modo a obter um subgrafo gerador bipartido é conhecido na literatura [Doslic and Vukicevic 2007] como o Problema de Frustração de Arestas. Neste trabalho, abordamos o Problemas da Frustração de Arestas em grafos (3, 6)- fullerenes. Mostramos que todo grafo (3, 6)-fullerene com n vértices torna-se bipartido após a retirada de no máximo q4 3n arestas.