Color $E(K_6)$ by three colors without colorful triangle

coloringcombinatoricsgraph theory

We color $E(K_6)$, the edge set of the complete graph with six vertices, by three colors (say red, blue, and green) and each color should be used once so that there is no triangle whose edges are colorful (no triangle has one red, one blue, and one green edge).

For example, we can color all the edges incident to a vertex with red. And in the remaining $K_5$, we color a 5-cycle $C_5$ by blue and the remaining $C_5$ by green.

I tried some colorings, and I am wondering if it is true that for any such coloring (edge coloring of $K_6$ without colorful triangle), there must be a vertex so that all edges incident to it are in the same color?
Edit: This guess is false.

New guess: there is a partition of the six vertices into two parts $A,B$ such that the edges between $A$ and $B$ are in one color? (In the first guess, $|A|=1$.)

Any known result in this field?

Best Answer

In general, edge-colorings of the complete graph without a tricolored triangle are called Gallai colorings. These are studied generally, not just with three colors available, though if we only use $2$ colors the problem is a bit easy :)

The paper Edge Colorings of Complete Graphs Without Tricolored Triangles by Gyárfás and Simonyi gives a good overview and in particular contains a proof of the following result (Theorem A in the paper):

Any Gallai coloring can be obtained by substituting complete graphs with Gallai colorings into vertices of $2$-colored complete graphs.

Let me elaborate on this idea. It is a way of building bigger Gallai colorings out of smaller ones. Suppose we have already found Gallai colorings of complete graphs on $n_1, n_2, \dots, n_k$ vertices. (Sometimes $n_i = 1$, in which case there is nothing to color; that's fine.) We also take an arbitrary $2$-coloring of the complete graph on $k$ vertices; that will be our "glue". Call the small Gallai colorings $C_1, C_2, \dots, C_k$ and call the "glue" $G$.

Now, to color the complete graph on $n_1 + n_2 + \dots + n_k$ vertices, begin by placing disjoint copies of $C_1, C_2, \dots, C_k$. What's left is to color the edges between these copies. For this, we give all the edges between $C_i$ and $C_j$ the same color: the color of edge $ij$ in $G$.

Any triangle in the resulting coloring has one of three types:

  1. It could be entirely contained in a small Gallai coloring, in which case it is not tricolored by assumption.
  2. It could have two vertices in one small coloring $C_i$ and the third in another, $C_j$; then two of its edges get their color from edge $ij$ of $G$, and have the same color.
  3. It could have all three vertices in different small colorings; then all three of its edges are colored using $G$, which only has $2$ colors.

The really interesting bit is that this recipe gives us all the possible Gallai colorings.

The recipe also lets us disprove other conjectures we might have about Gallai colorings. For example, in a three-color Gallai coloring of $K_6$, it is not necessarily true that some partition $A,B$ exists where all edges between $A$ and $B$ are the same color. One way to get there is to color $K_5$ by coloring a $5$-cycle red and its complement blue. Then, substitute a green edge in place of one of the vertices of $K_5$, as described above.

Related Question