The number of Gallai k-colorings of complete graphs

Autor(es)

Bastos, Josefran de Oliveira ^[1] ; Benevides, Fabricio Siqueira ^[2] ; Han, Jie ^[3]

Afiliação do(s) autor(es)

^[1] Univ Fed Ceara, Engn Comp, Fortaleza, Ceara - Brazil

^[2] Univ Fed Ceara, Dept Matemat, Fortaleza, Ceara - Brazil

^[3] Univ Rhode Isl, Dept Math, Kingston, RI 02881 - USA

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF COMBINATORIAL THEORY SERIES B; v. 144, p. 1-13, SEP 2020.
• Citações Web of Science: 0

Resumo

An edge coloring of the n-vertex complete graph, K-n, is a Gallai coloring if it does not contain any rainbow triangle, that is, a triangle whose edges are colored with three distinct, colors. We prove that for n large and every k with k <= 2(n/)(4300), the number of Gallai colorings of K-n that use at most k given colors is (((k)(2)) + o(n) (1)) 2((2n)). Our result is asymptotically best possible and implies that, for those k, almost all Gallai k-colorings use only two colors. However, this is not true for k >= 2(n/2). (C) 2020 Elsevier Inc. All rights reserved. (AU)

• Processo FAPESP: 14/18641-5 - Circuitos hamiltonianos e problemas de ladrilhamento em hipergrafos
• Beneficiário: Jie Han
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado