A note on balanced edge-colorings avoiding rainbow cliques of size four

2023/03/26 by Felix Christian Clemen, Adam Zsolt Wagner, Clemen, Felix Christian +1
Engineering · #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2303.15476

openalex publication_date 2023/03/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A balanced edge-coloring of the complete graph is an edge-coloring such that every vertex is incident to each color the same number of times. In this short note, we present a construction of a balanced edge-coloring with six colors of the complete graph on n=13^k vertices, for every positive integer k, with no rainbow K₄. This solves a problem by Erdős and Tuza.

Related

• Rainbow Subgraphs in Edge-colored Complete Graphs -- Answering two Questions by Erdős and Tuza
• An explicit edge-coloring of K_n with six colors on every K₅
• A note on large rainbow matchings in edge-coloured graphs
• Rainbow Cliques in Edge-Colored Graphs
• On the balanced upper chromatic number of finite projective planes