Proper edge colorings of complete graphs without repeated triangles

  • Fábio Botler UFRJ
  • Lucas Colucci USP
  • Paulo Matias UFABC
  • Guilherme Mota USP
  • Roberto Parente USP / UFBA
  • Matheus Secco

Resumo


In this paper, we consider the problem of computing the minimum number of colors needed to properly color the edges of a complete graph on $n$ vertices so that there are no pair of vertex-disjoint triangles colored with the same colors. This problem was introduced recently (in a more general context) by Conlon and Tyomkyn, and the corresponding value was known for odd $n$. We compute this number for another infinite set of values of $n$, and discuss some small cases.

Referências

Biere, A. (2018). Lingeling, Plingeling and Treengeling. http://fmv.jku.at/lingeling.

Conlon, D. and Tyomkyn, M. (2020). Repeated patterns in proper colourings. arXiv preprint arXiv:2002.00921.

The Sage Developers (2020). SageMath, the Sage Mathematics Software System (Version 9.1). https://www.sagemath.org.
Publicado
31/07/2022
BOTLER, Fábio; COLUCCI, Lucas; MATIAS, Paulo; MOTA, Guilherme; PARENTE, Roberto; SECCO, Matheus. Proper edge colorings of complete graphs without repeated triangles. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 65-68. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2022.222917.