Search

We introduce classes of edge-colourings of the complete graph—that we call nice and beautiful—and study how many heterochromatic spanning trees appear under such colourings. We prove that if the colouring is nice, there is at least a quadratic number of different heterochromatic trees; and if the colouring is beautiful there is an exponential number of different such trees. [ABSTRACT FROM AUTHOR]

An edge colouring of a graph G is complete if for any distinct colours c1 and c2 one can find in G adjacent edges coloured with c1 and c2, respectively. The pseudoachromatic index of G is the maximum number of colours in a complete edge colouring of G. Let ψ(n) denote the pseudoachromatic index of Kn. In the paper we proved that if x≥2 is an integer and n∈{4x2-x,⋯,4x2+3x-3}, then ψ(n)≤2x(n-x-1). Let q be an even integer and let ma=(q+1)2-a. If there is a projective plane of order q, a complete edge colouring of Kma with (ma-a)q colours, a∈{-1,0,⋯,q2+1}, is presented. The main result states that if q≥4 is an integer power of 2, then ψ(ma)=(ma-a)q for any a∈{-1,0,⋯,1+4q+92-1}. [ABSTRACT FROM AUTHOR]

Abstract: Let and . Further, let be the complete line graph and its pseudoachromatic number. By exhibiting an explicit colouring of , we show that . This result improves the bound due to Jamison (1989) [Jamison, R.E.; On the edge achromatic numbers of complete graphs, Discrete. Math. 74 (1989) 99–115]. [Copyright &y& Elsevier]