Coloring cliques of a clique decomposition of the complete graph

Question

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?

Answer 1

This question is equivalent to the famous (and unsolved) Erdos-Faber-Lovasz 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.