O wykresach, których zestaw krawędzi rozkłada się w idealne dopasowania

Czy istnieje charakterystyka wykresów, których zestaw krawędzi rozkłada się w rozłączny związek idealnych dopasowań?

Jedną trywialną klasą takich grafów są $d$-nieregularne -obustronne wykresy. Ich zestaw krawędzi rozpadnie się na rozłączne idealne dopasowania. $(n,n)$$d$

Tak: nazywamy takie wykresy 1-czynnikowym (1-czynnik jest również znany jako idealne dopasowanie). Wszystkie takie wykresy są regularne, ale odwrotność nie jest prawdziwa. W rzeczywistości a$d$-regularny wykres $G$ jest 1-czynnikowy tylko wtedy, gdy jest pierwszej klasy, to znaczy $\chi'(G) = d$, gdzie $\chi'(G)$ jest indeksem chromatycznym $G$.

Decydowanie, czy $d$- nieregularny wykres klasy 1 jest NP-kompletny (patrz np. [1]), więc prawdopodobnie nie można tego skutecznie przetestować.

[1] Leven, Daniel i Zvi Galil. „Kompletność NP znalezienia wskaźnika chromatycznego zwykłych wykresów”. Journal of Algorithms 4.1 (1983): 35-44.