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

      0 references
      28 March 1993
      0 references
      complete, proper edge coloring
      0 references
      achromatic number
      0 references
      achromatic index
      0 references
      lower bound
      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

      Identifiers