A343607 Minimal number of colors required for an edge-coloring of the complete graph K_n with no monochromatic triangle.

0, 0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4

Offset: 0

Author

M. F. Hasler, Jun 25 2021

Keywords

• nonn
• more

Comments

The complete graph K_n has n(n-1)/2 edges (i,j), 1 <= i < j <= n, connecting the n vertices to each other. A triangle is a subgraph of edges {(i,j), (i,k), (j,k)} with i < j < k; monochromatic means that all edges have the same color.

The edge-colorings are obviously not required to be proper, i.e., adjacent edges may have the same color.

Corollary 3 of Cummings et al. (2013) gives a formula for an upper bound on M_3(K_3,n), the minimal number of monochromatic triangles in a 3-colored K_n, which is positive iff n >= 11 (which, if tight, would mean a(n) > 3 for n > 10). However, the paper only claims that the bound is tight for all sufficiently large n. We have indeed 3-edge-colorings up to n = 16 with no monochromatic triangle. It is known that a(n) > 3 iff n = 17, cf. A343606.

Rows of A343606 give the lexicographic earliest edge-colorings of K_n without monochromatic triangles using the minimum number of colors a(n).

Examples

			For n = 0 and n = 1, the empty graph K_0 and the singleton graph K_1 don't have any edge, so zero colors are needed.
For n = 2 we have one edge, so one color is needed.
For n = 3 we have a triangle, so we need a second color for the third edge.
For n = 4 (square + diagonals) and n = 5 (pentagon + diagonals forming a pentagram) two colors are still enough: one can use one color for the "circumference", i.e., edges (i,i+1), and the other color for the diagonals.
For n >= 6, a third color is needed.
		

Links

• James Cummings, Daniel Král', Florian Pfender, Konrad Sperfeld, Andrew Treglown and Michael Young, Monochromatic triangles in three-coloured graphs, Journal of Combinatorial Theory B 103 no. 4 (2013) 489-503 (also: arXiv:1206.1987).
• Wikipedia, Monochromatic triangle.

Crossrefs

Cf. A343606 (gives corresponding colorings), A000217 (triangular numbers - row lengths of A343606), A003323.

Programs

PARI

A343607(n)=if(n>1, vecmax(color(n))+1, 0) \\ using the helper function:
{M343607=List([[]]); color(n, i=matrix(n,n,r,c,r+c--*c--/2), C, k)= C|| C = if(#M343607 >= n, M343607[n], n>2, color(n-1,i)); k|| k=if(n>3, vecmax(C)+1, n-1); C=Vec(C, n*(n-1)/2); my(bad(C)= for(a=1,n-2, my(c=C[i[a,n]]); for(b=a+1, n-1, C[i[a,b]] !=c || C[i[b,n]] !=c || return( i[b,n] ))), C0=C, j); while(j=bad(C), until(j-- < i[1,n], if(C[j]++ < k, while(j<#C, C[j++]=0); next(2))); while(C[j]++ >= k, C[j]=0; j--); C=Vec(color(n-1,i,C[1..-n]),#C); if(C[1..n] != C0[1..n], k++; C=C0)); #M343607= 13. Changing 1..n to 1..2-2*n is much faster but yields suboptimal solution for n >= 12 (using 4 instead of 3 required colors).

Formula

a(n) = max { A343606(n,k)+1; k >= 1 } U { 0 }.

a(n) = min {k >= 0; A003323(k) > n}. - Pontus von Brömssen, Aug 01 2021

Extensions

More terms from Pontus von Brömssen, Jul 21 2021