On \(m\)-Chromatic Factorizations of Complete Graphs

Abstract

For a factorization \( F \) of a graph \( G \) into factors \( F_1, F_2, \ldots, F_k \), the chromatic number \( \chi(F) \) of \( F \) is the minimum number of elements \( V_1, V_2, \ldots, V_m \) in a partition of \( V(G) \) such that each subset \( V_i \) \((1 \leq i \leq m)\) is independent in some factor \( F_j \) \((1 \leq j \leq k)\). If \( \chi(F) = m \), then \( F \) is an \( m \)-chromatic factorization.

For integers \( k, m, n \geq 2 \) with \( n \geq m \), the cofactor number \( c_m(k,n) \) is defined as the smallest positive integer \( p \) for which there exists an \( m \)-chromatic factorization \( F \) of the complete graph \( K_p \) into \( k \) factors \( F_1, F_2, \ldots, F_k \) such that \( \chi(F_i) \geq n \) for all integers \( i \) \((1 \leq i \leq k)\). The values of the numbers \( c_m(k,n) \) are investigated for \( m = 3 \) and \( m = 4 \).

The \( k \)-cofactorization number \( \chi_k(G) \) of a graph \( G \) is defined as \( \max\{\chi(F) : F \text{ is a factorization of } G \text{ into } k \text{ factors}\} \). It is shown that \( \chi_k(K_n) \geq \lfloor n^{1/k} \rfloor \) for \( k \geq 2 \) and \( n \geq 4 \). The numbers \( \chi_k(K_n) \) are determined for several values of \( k \) and \( n \).