Colorful edge decomposition of graphs: Some polynomial cases

In this work, we investigate some properties of this edge decomposition. We prove that for each t, every tree has a colorful t-edge decomposition and that decomposition can be found in polynomial time. On the negative side, we prove that for a given graph G with 2≤δ(G)≤Δ(G)≤3 determining whether G has a colorful 2-edge decomposition is NP-complete. Among other results, we show that for a given bipartite graph G with degree set {a1,a2,…,ac} where c is a constant number, if for each i, 1≤i≤c, the induced subgraph on the set of vertices of degree ai has d connected components, where d is a constant number, then there is a polynomial time algorithm to decide whether G has a colorful 2-edge decomposition. Also, we prove that every r-regular graph G with at most one cut edge has a colorful 2-edge decomposition.