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

DOI: https://doi.org/10.5753/etc.2022.222917

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.