Counting Gallai 3-colorings of complete graphs

Autor(es)

Bastos, Josefran de Oliveira ^[1] ; Benevides, Fabricio Siqueira ^[2] ; Mota, Guilherme Oliveira ^[3] ; Sau, Ignasi ^[4]

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 Fed ABC, Ctr Matemat Comp & Cognicao, Santo Andre - Brazil

^[4] Univ Montpellier, CNRS, LIRMM, Montpellier - France

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE MATHEMATICS; v. 342, n. 9, p. 2618-2631, SEP 2019.
• 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 the number of Gallai colorings of K-n with at most three colors is at most 7(n + 1)2((n2)), which improves the best known upper bound of 3/2(n - 1)! . 2((n-12)) in Benevides et al. (2017). (C) 2019 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 18/04876-1 - Teoria de Ramsey, teoria estrutural de grafos e aplicações em Bioinformática
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores