Acerca de los gráficos cuyo conjunto de bordes se descompone en combinaciones perfectas

9

¿Existe una caracterización de gráficos cuyo conjunto de bordes se descomponga en una unión disjunta de combinaciones perfectas?


Una clase trivial de tales gráficos son los gráficos -regulares ( n , n ) -bipartitos. Su conjunto de bordes se descompondrá en d combinaciones perfectas disjuntas. re(norte,norte)re

usuario6818
fuente

Respuestas:

6

Sí: llamamos a estos gráficos 1 factorizable (un factor 1 también se conoce como una coincidencia perfecta). Todos estos gráficos son regulares, pero lo contrario no es cierto. De hecho, un gráfico -regular G es 1-factorizable si y sólo si es de una clase, que es, χ ' ( G ) = d , donde χ ' ( G ) es el índice cromático de G .resolχ(sol)=reχ(sol)sol

Decidir si un gráfico regular es de clase 1 es NP-completo (ver, por ejemplo, [1]), por lo que es probable que no pueda probar esto de manera eficiente.re


[1] Leven, Daniel y Zvi Galil. "NP completitud de encontrar el índice cromático de gráficos regulares". Journal of Algorithms 4.1 (1983): 35-44.

Juho
fuente
¡Gracias por la respuesta! (1) ¿Tiene una referencia para una prueba de esta integridad de NP? (2) ¿Parece que también hay otras clases? ¿Alguna referencia pedagógica para estos? (3) ¿Sabe si se sabe algo especial sobre el politopo de coincidencia perfecta de tales gráficos de 1 factor?
user6818
No, esto es una caracterización. Es decir, no hay otras clases de gráficos. La clase de gráficos de 1 factor es exactamente la clase de gráficos d -edge-colorable -regular . No creo saber nada mejor que lo que ofrece Wikipedia, ver por ejemplo aquí . rere
Juho