Sobre gráficos cujo conjunto de arestas se decompõe em combinações perfeitas

Existe uma caracterização de gráficos cujo conjunto de arestas se decompõe em uma união disjunta de combinações perfeitas?

Uma classe trivial de tais gráficos são os gráficos partidos regulares . Seu set borda irá se decompor em disjuntos perfeitos matchings. ( n , n ) $d$$(n,n)$$d$

Sim: chamamos esses gráficos de fator 1 (um fator 1 também é conhecido como uma correspondência perfeita). Todos esses gráficos são regulares, mas o inverso não é verdadeiro. Na verdade, um gráfico -Regular é 1-factorável se e só se for de uma classe, ou seja, , onde é o índice cromático de .G χ ′ ( G ) = d χ ′ ( G ) $d$$G$$\chi'(G) = d$$\chi'(G)$$G$

Decidir se um gráfico regular é da classe 1 é NP-completo (consulte, por exemplo, [1]), portanto você provavelmente não poderá testá-lo com eficiência.$d$

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