Über Diagramme, deren Kantenmenge sich in perfekte Übereinstimmungen zerlegt

Gibt es eine Charakterisierung von Graphen, deren Kantenmenge sich in eine disjunkte Vereinigung perfekter Übereinstimmungen zerlegt?

Eine triviale Klasse solcher Graphen sind reguläre ( n , n ) -teilige Graphen. Deren Rand gesetzt , zersetzen sich in d disjoint perfekt passende. $d$$(n,n)$$d$

Ja, wir nennen solche Graphen 1-faktorisierbar (ein 1-Faktor wird auch als perfekte Übereinstimmung bezeichnet). Alle diese Graphen sind regelmäßig, aber das Gegenteil ist nicht der Fall. Tatsächlich ist ein -regulärer Graph G genau dann 1-faktorisierbar, wenn er der Klasse 1 angehört, dh χ ' ( G ) = d , wobei χ ' ( G ) der chromatische Index von G ist .$d$$G$$\chi'(G) = d$$\chi'(G)$$G$

Die Entscheidung, ob ein regulärer Graph der Klasse 1 entspricht, ist NP-vollständig (siehe z. B. [1]), sodass Sie dies wahrscheinlich nicht effizient testen können.$d$

[1] Leven, Daniel und Zvi Galil. "NP-Vollständigkeit beim Finden des chromatischen Index regulärer Graphen." Journal of Algorithms 4.1 (1983): 35 & ndash; 44.