scientific article; zbMATH DE number 139930
[For the entire collection see Zbl 0747.00032.] A coloring of the edges of the complete graph \(K_ n\) is proper iff no two edges with a common endnode get the same color. An edge coloring is complete iff for any two colors \(c_ 1\) and \(c_ 2\), there are two edges with a common endnode, one colored \(c_ 1\) and the other colored \(c_ 2\). The maximum number of colors in a complete, proper edge coloring of \(K_ n\) is the achromatic index \(A(n)\) of \(K_ n\). The determination of the achromatic number is generally quite difficult. Even the special case of the achromatic index \(A(n)\) of \(K_ n\) can be formidable, as the following remarkable result of \textit{André Bouchet} [Cah. Cent. Etud. Rech. Oper. 20, 331-340 (1978; Zbl 0404.05026)] shows: Theorem. Suppose \(q\) is an odd integer and \(n=q^ 2+q+1\). Then \(A(n)\leq qn\) with equality if and only if a projective plane of order \(q\) exists. In particular, this yields \(A(13)=39\). Several authors have investigated \(A(n)\) for small \(n\) and exact values are known for \(n\leq 11\). Currently [the author, Discrete Math. 74, No. 1/2, 99-115 (1989; Zbl 0667.05024)], it is known that \(31\leq A(12)\leq 33\). Here we will improve the lower bound to 32 and investigate some of the properties of a complete 33- coloring if one exists.
- On the edge achromatic numbers of complete graphs
- On upper bounds for the pseudo-achromatic index
- On the pseudoachromatic index of the complete graph. III
- On the achromatic index of \(K_{q^2+q}\) for a prime \(q\)
- The achromatic indices of the regular complete multipartite graphs
- Achromatic numbers for circulant graphs and digraphs
- scientific article; zbMATH DE number 4097414 (Why is no real title available?)
- scientific article; zbMATH DE number 1409196 (Why is no real title available?)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4028277)