Let $G=K\_k$, the complete graph on $k$ vertices. Consider the cliques induced by the sets of edges of a clique decomposition of $G$. Can you $k$-color the edges of $G$ so that each of the cliques in question is monochromatic, and so that if two distinct cliques share a vertex, their edges receive different colors? If the answer is yes, how do you prove it?



Coloring cliques of a clique decomposition of the complete graph
This question is equivalent to the famous (and unsolved) [Erdos-Faber-Lovasz conjecture](https://en.m.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Faber%E2%80%93Lov%C3%A1sz_conjecture). So resolving your question would be great, but likely difficult.


That conjecture has many formulations, but here’s one that sounds most like yours...



> 
> **EFL conjecture:** Suppose $E\_1, E\_2, ..., E\_t$ are subsets of $\{1,2,\ldots, k\}$ each having size at least 2, and suppose that $|E\_i \cap E\_j | \leq 1$ for all distinct $i,j$. Then we can assign each set $E\_i$ a color between 1 and k such that if two sets intersect, they receive different colors.
> 
> 
> 


To connect the two problems, for any clique decomposition of $K\_k$, let each $E\_i$ denote one of the cliques you used. So EFL would imply the answer to OP is yes.


On the other hand, suppose the answer to your question is yes. Let $E\_1, \ldots, E\_t$ satisfy the hypotheses of the EFL conjecture. Then we can always add sets of size 2 (if needed) to this collection until every 2-element subset of $\{1,\ldots ,k\}$ is contained in some set $E\_i$ (and doing so couldn’t decrease the chromatic index of the set system). Thus, we may assume the sets $E\_i$ cover every 2-element subset exactly once, which means they correspond to a clique decomposition of $K\_k$. So your question would imply the EFL conjecture.


Thus, the question is equivalent to EFL.




---


That said, hope isn’t lost. There are partial results known about EFL. Perhaps most notably is the result of Kahn that such a coloring exists if you allow yourself to use $k+o(k)$ colors.


