Originators: Robert Jamison (presented by Robert Jamison - REGS 2011)
Definitions:
A proper coloring of the vertices of a graph assigns colors to the
vertices so that adjacent vertices have different colors. In a
complete coloring, for every pair of colors there is some edge whose
endpoints have those colors; note that every proper coloring using the fewest
colors is complete. The achromatic number of a graph is the maximum
number of colors in a proper complete coloring of the vertices. The
edge-achromatic number or achromatic index of a graph is the
achromatic number of its line graph. In the case of Kn,
we seek to color the edges so that
1) incident edges have distinct colors, and
2) any two distinct colors occur on some two incident edges.
Let A(n) denote the achromatic index of Kn.
Background: The exact value of A(n) is known for n ≤ 13, for n having the form n = q²+q+1 where q is the order of a projective plane, and (by a special construction due to Bouchet) for n=25 (in fact, A(25)=100). (For A(12)=32, the lower bound appears in [J], and the upper bound was proved by Hornak.)
It is easy to see that A(n+1) ≥ A(n). This and the values given by projective planes imply that A(n) is asymptotic to n3/2. Thus A(n+1) - A(n) must be large for some values of n, but in general no lower bound is known.
Problem: Show that A(n+1) ≥ A(n)+1.
Comments: Only the following weaker result is known ([J]): A(n+2) ≥ A(n) + 2 for n > 4.
It would be natural also to study the achromatic index of Kn,n. The desired colorings can be expressed as n-by-n grids of labels such that each label appears at most once in each row and column, and every two labels that are used occur together in some row or some column. Hedetniemi may have worked on this.
References:
[J] Robert E. Jamison,
On the edge achromatic numbers of complete graphs,
Discrete Math. 74(1989), 99--115.