Split and balanced colorings of complete graphs
An \((r,n)\)-split coloring of a complete graph is an edge coloring such that the vertex set can be partitioned into \(r\) parts with the \(i\)th part not containing a monochromatic \(K_n\) in color \(i\). The smallest \(N\) such that \(K_N\) has an \((r,n)\)-split coloring is denoted by \(f_r(n)\). The function \(f_r\) is investigated; in particular, it is shown that \(f_2(n) = n^2\) and \(f_r(2) > {r \choose 2}\). A related function \(g_r(n)\), which is the smallest \(N\) such that there exists an edge coloring of \(K_N\) so that every subset of \(\lceil N/r \rceil\) vertices contains a monochromatic \(K_n\) in each color, is also studied. Since \(f_r(n) \leq g_r(n)\), upper bounds on \(g_r(n)\) give bounds on \(f_r(n)\). The bounds \(r^2 + 1 \leq g_4(2) \leq r^2 + r + 1\) are verified. Also, some small order numbers are determined; for example, \(f_3(2) = 8\), \(g_3(2) = 13\), and \(g_4(2) = 21\).
scientific article; zbMATH DE number 1334442
scientific article