¿cuándo un gráfico regular tiene una factorización 1?

Question

¿Existe una condición suficiente para que un grafo regular tenga una factorización 1 (es decir, que pueda empaquetar todas sus aristas en parejas perfectas disjuntas, y excluir un vértice si el número de vértices es impar)?

Answer 1

Ser un grafo completo con un número par de vértices es una condición suficiente. Dicho esto, comprobar si un grafo 3-regular es 3-edge-colorable es NP-difícil ( http://dx.doi.org/10.1016/j.ipl.2008.05.015 )

Puedes tener certificados de que un grafo requiere más de 3 colores calculando su índice cromático fraccionario (factible en tiempo polinómico con un solucionador LP y un algoritmo de correspondencia ponderada máxima a mano). Se trata de comprobar si el grafo contiene un subgrafo sobrelleno ( http://en.wikipedia.org/wiki/Overfull_graph )

Para ello, puede echar un vistazo a :

Daniel Ullman y Edward Scheinerman - Teoría de grafos fraccionarios

http://www.ams.jhu.edu/~ers/fgt/fgt.pdf

Nathann

Answer 2

Quizá ya lo sepas, pero cada bipartito es 1-factible (véase, por ejemplo. estas notas de clase ).