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?


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.

  • 1
    $\begingroup$ Thanks. I realized just a little while before your answer came in that EFL was equivalent to the problem posted. As you say, not all hope is lost ... this equivalent formulation can be found in a paper of Hindman in CJM (1981). I should have looked deeper at first. I am also aware of the Kahn asymptotic result you mention. But, let’s see, there are some structures recently proposed (in unpublished manuscripts that I have received related to another problem) that make me hope that this problem will one day be solved. $\endgroup$ – EGME May 11 at 17:24
  • $\begingroup$ I agree. It’ll be proven. Especially because Kahn’s result makes me believe it’s true! $\endgroup$ – Pat Devlin May 11 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.