Anti-Ramsey theorems on big double stars and on long paths
by
Balazs Montagh
University of Memphis

Erdös, Simonovits and Sós have initiated the investigation of anti-Ramsey problems for graphs. We say that a graph is totally multicolored (TMC, for short) if any two of its edges have different colors. Given a family L of graphs, let AR(n, L) be the largest integer t for which it is possible to t-color the edges of K_n so that every color is used at least once, and there is no TMC subgraph that belongs to L. It is easy to see that AR(n, L) >= ex(n, L^*)+1, where L^*={L-e:L in L, e in E(L)}.

Let T_m be the family of all trees with k edges, and let T^d_m be the family of all trees with m edges of diameter at most d. Jiang and West have determined the numbers AR(n, T_m). They have found that AR(n, T_m)=ex(n, T^*_m)+1. The case k=n-1, that is, the case of spanning trees, was solved independently by Bialostocki and Voxman. Bialostocki conjectured that AR(n, T_n-1)=AR(n, T⁴_n-1).

We prove that much more is true. First of all, AR(n, T_n-1)=AR(n, T³_n-1). Furthermore, AR(n, L)=AR(n, T_n) holds even for a family L that is much smaller than T³_n, in fact, for a family with |L|=4. Let DS^k_m be the families of double stars (that is, trees of diameter 3) with m edges whose maximal degree is at least k. We shall show that AR(n, T_n-1)=AR(n, DS^n-4_n-1) < AR(n, DS^n-3_n-1). Our method works also in the case when the trees are a bit smaller than the spanning trees: we proved that if n > 11k/2+7 then AR(n, T_n-k)=AR(n, DS^n-2k-2_n-k) < AR(n, DS^n-2k-1_n-k).

We prove a similar theorem for a concrete graph: if if n > k²+7k-1 then AR(n, P_n-k)=AR(n, T_n-k)=((n-k-1) || 2)+1. This is an expansion of a part of a theorem of Simonovits and Sós that was published without proof.

Date received: April 20, 2001