No label defined (Q4028277)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 139930
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 139930 |
Statements
28 March 1993
0 references
complete, proper edge coloring
0 references
achromatic number
0 references
achromatic index
0 references
lower bound
0 references
0.8908863663673401
0 references
0.878280520439148
0 references
0.854945719242096
0 references
0.854945719242096
0 references
[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.
0 references