Consider a graph . G and a labeling of its edges with . r labels. Every vertex . v∈V(G) is associated with a palette of incident labels together with their frequencies, which sum up to the degree of . v. We say that two vertices have distinct palettes if they differ in the frequency of at least one label, otherwise they have the same palette. For an integer . r>0, a colorful . r-edge decomposition of a graph . G is a labeling . ℓ:E(G)→(1,...,r) such that for any vertex . v∈V(G), the edges incident with the vertex . v have at least . min(r,d(v)) different labels and for every two adjacent vertices . v and . u with . d(v)=d(u), they have the same palette.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.

Additional Metadata
Keywords Colorful edge decomposition, Graph decomposition, Palette, Polynomial algorithm, Totally unimodular matrix
Persistent URL dx.doi.org/10.1016/j.dam.2016.10.019
Journal Discrete Applied Mathematics
Citation
Dehghan, A. (Ali), & Sadeghi, M.-R. (Mohammad-Reza). (2015). Colorful edge decomposition of graphs: Some polynomial cases. Discrete Applied Mathematics. doi:10.1016/j.dam.2016.10.019