Partition des bords en triangles arc-en-ciel

Je me demande si le problème suivant est NP-difficile.

Entrée: $G = (V,E)$ un graphe simple, et une coloration $f : E \to \{1,2,3\}$ des arêtes ( $f$ ne vérifie aucune propriété spécifique).

Question: est-il possible de partitionner $E$ en $|E|/3$ triangles, de sorte que chaque triangle ait un bord de chaque couleur?

Je sais que sans les couleurs, le problème de la "partition de bord" un graphe en , n ≥ 3 est NP-difficile (voir La NP-Complétude de certains problèmes de partition de bord ) mais avec les couleurs que je ne connais pas.$K_n$$n \geq 3$

Je serais également intéressé par un résultat pour le partitionnement des bords en arc-en-ciel , avec c une constante. Bien sûr, dans ce cas, le problème devient:$K_c$$c$

$G = (V,E)$$f : E \to \{1,\ldots,c(c-1)/2\}$$f$

$E$$|E|/(c(c-1)/2)$ $K_c$$K_c$

$K_n$$K_n$$K_n$$K_n$$K_n$

La structure de base de la réduction de ce papier peut être accomplie avec les 3 étapes suivantes:

1. $H_{n,p}$
2. $H_{n,p}$$H_{n,p}$
3. Supprimez certains sommets / bords de certaines copies.

$H_{n,p}$$n$$p$$0$$p$$+1$$-1$

$x$$y$$x-y$$n-2$$0$$1$$-1$$(x, y)$${n \choose 2}$$x-y$$K_n$$H_{n,p}$$K_n$$H_{n,p}$$K_n$

$H_{n,p}$$K_n$$K_n$

$K_n$$K_n$$K_n$$H_{n,p}$$K_n$$K_n$$K$$-K$$K_n$$K_n$$K_n$$K_n$$K_n$$K_n$

$K_n$$K_n$$K_n$