|
| |
|
|
A343606
|
|
Row n gives the lexicographically earliest edge coloring of the complete graph K_n with no monochromatic triangle.
|
|
2
|
|
|
|
0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 2, 0, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 2, 0, 2, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 1, 0, 1, 2, 0, 2, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 2, 0, 2, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0, 1, 1, 2, 0, 0, 0, 0, 1, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,26
|
|
|
COMMENTS
|
The complete graph K_n has (n-1) + (n-2) + ... + 1 = n(n-1)/2 edges connecting the n vertices to each other. We associate a color to each edge such that there is no monochromatic triangle, i.e., no three vertices i < j < k such that the tree edges (i,j), (i,k) and (j,k) all have the same color.
For each n, consider the smallest possible number k of colors allowing such an edge-coloring. This table lists in row n, of length n(n-1)/2, the lexicographic earliest such coloring, i.e., the colors (between 0 and k-1) of edges AB = (1,2), AC = (1,3), BC = (2,3), ..., AZ = (1,n), ..., YZ = (n-1,n).
This is the lower left part (read by rows) or the upper right part (read by columns) of the symmetric n X n matrix where the element with indices (i,j) gives the color of the edge (i,j).
We conjecture that the rows converge to a limit in the sense that an increasingly long initial segment will always remain constant for all subsequent rows: for all k >= 0 there is n such that a(m,j) = a(n,j) for all m >= n and 1 <= j <= k.
Obviously, the first element a(n,1) = 0 for all n >= 2, and the first three elements will always be a(n, 1..3) = (0, 0, 1) for all n >= 3.
It seems that for n = 6 and n = 7, too, we have a(m,k) = a(n,k) for all m >= n and 1 <= k <= n(n-1)/2. Are there other row indices with this property? (This is of course much stronger than the requirement of convergence.)
Let us call min-color any solution that uses the minimum number of colors for the respective n. The restriction of any row n to the length of an earlier row m < n is always a solution for m, but not necessarily min-color: For n = 5 we have a solution using only 2 colors, but the lex earliest solutions for n >= 6 use 3 colors among the edges between the first 4 vertices. However, the lex earliest solution for n = 5, using only 2 colors, can be extended to solutions for all n >= 6. But the lex earliest solution for n = 4 cannot be extended to a min-color solution for n = 5.
Can one or the other of the following conjectures be (dis)proved?
Conjecture 1: For any n there is a min-color solution that can be extended to a min-color solution for all larger m > n?
Conjecture 2 (implies conjecture 1): For any n there is a min-color solution that can be restricted to a min-color solution for any smaller m < n.
Since Conjecture 2 does not make any assumption about the lexicographical order, it is independent of the convergence of the rows of this sequence mentioned above.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
Rows n = 0 and n = 1 have length n(n-1)/2 = 0, since the empty graph K_0 and the singleton graph K_1 have no edges.
Starting with n = 2, the graph K_n has a positive number n(n-1)/2 of edges:
n | Coloring of edges (1,2) = AB, (1,3) = AC, (2,3) = BC, ..., (n-1,n) = YZ
---+------------------------------------------------------------------------
2 | 0 (The only non-diagonal element, in row/col. 2 of the color matrix.)
3 | 0; 0, 1 (Rows 2 and 3 of the subdiagonal part of the color matrix.)
4 | 0; 0, 1; 1, 0, 0 (Rows 2, 3 and 4 below the diagonal of that matrix.)
5 | 0; 0, 1; 1, 0, 1; 1, 1, 0, 0
6 | 0; 0, 1; 0, 1, 2; 0, 2, 1, 1; 1, 0, 0, 0, 0
7 | 0; 0, 1; 0, 1, 2; 0, 2, 1, 1; 1, 0, 0, 0, 0; 1, 0, 0, 0, 0, 2
8 | ...; 2, 0, 0, 0, 0, 1, 1 (where ... = row 7)
9 | ...; 2, 0, 0, 0, 0, 1, 2; 2, 0, 0, 0, 0, 2, 1, 1
10 | ...; 2, 0, 0, 0, 0, 1, 2; 2, 0, 0, 0, 1, 2, 1, 1; 2, 2, 1, 1, 0, 2, 1, 1, 0
11 | ...; 2, 0, 0, 0, 1, 1, 2; 2, 0, 0, 0, 2, 2, 1, 1; 2, 2, 1, 2, 0, 2, 1, 1, 0
| ; 2, 2, 2, 1, 0, 2, 1, 0, 0, 1
The graph K_2 consists of only one edge with color 0.
The graph K_3 is a triangle, two edges get color 0, the third one color 1.
The graph K_4 is a square with its two diagonals; the edges AB, AC, BC, AD, BD and CD get colors 0, 0, 1, 1, 0 and 0, respectively.
The given solution for n = 5 can be extended to a solution for n = 6 by appending [0, 1, 2, 0, 2]. This solution comes lexicographically later because edges AD, BD, CD (row 4/col. 4 of the "color matrix") are colored (1, 0, 1) instead of (0, 1, 2), but uses only 2 colors for all edges not adjacent to the last vertex F.
|
|
|
PROG
|
(PARI) row(n)={ local(C=vector(n*(n-1)/2), k, i=matrix(n, n, i, j, if(i<j, k++)), bad()=for(a=1, n, for(b=a+1, n, k=C[i[a, b]]; for(c=b+1, n, C[i[a, c]] != k || C[i[b, c]] != k || return(i[b, c])))), c=1); while(k=bad(), until(!k-- || C[k] >= k, if(C[k]++<c, while(k<#C, C[k++]=0); next(2))); C*=0; c++); C}
|
|
|
CROSSREFS
|
Total number of elements in rows 0 through n is A000292(n-1).
Number of distinct colors in row n is A343607(n).
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
