On $m$-Chromatic Factorizations of Complete Graphs

Abstract

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

For integers $k,m,n\ge 2$ with $n\ge 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,\dots ,F_k$ such that $\chi (F_i)\ge n$ for all integers $i$ $(1\le i\le 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)\ge \lfloor n^{1/k}\rfloor$ for $k\ge 2$ and $n\ge 4$. The numbers ${\chi }_k(K_n)$ are determined for several values of $k$ and $n$.