À propos des graphiques dont le jeu d'arêtes se décompose en correspondances parfaites

Existe-t-il une caractérisation de graphes dont l'ensemble de bords se décompose en une union disjointe de correspondances parfaites?

Une classe triviale de tels graphes sont les graphes bipartites réguliers . Leur jeu de bord se décompose en disjoints filtrages parfait. $d$ $(n,n)$ $d$

graph-theory graphs user6818
la source

Réponses:

$d$ $G$ $\chi'(G) = d$ $\chi'(G)$ $G$

$d$

[1] Leven, Daniel et Zvi Galil. "Exhaustivité NP de la recherche de l'indice chromatique des graphes réguliers." Journal of Algorithms 4.1 (1983): 35-44.

Juho
la source

Merci pour la réponse! (1) Avez-vous une référence pour une preuve de cette complétude NP? (2) Il semble qu'il y ait aussi d'autres classes? Une référence pédagogique pour ceux-ci? (3) Savez-vous si quelque chose de spécial est connu sur le polytope parfaitement adapté de ces graphiques à 1 facteur?

user6818

d

$d$

d

$d$