Some bounds on convex combinations of $\omega$ and $\chi$ for decompositions into many parts

Abstract

A \emph{$k$--decomposition} of the complete graph $K_n$ is a decomposition of $K_n$ into $k$ spanning subgraphs $G_1,...,G_k$. For a graph parameter $p$, let $p(k;K_n)$ denote the maximum of $\sum _{j=1}^{k}p(G_j)$ over all $k$--decompositions of $K_n$. It is known that $\chi (k;K_n)=omega(k;K_n)$ for $k\le 3$ and conjectured that this equality holds for all $k$. In an attempt to get a handle on this, we study convex combinations of $\omega$ and $\chi$; namely, the graph parameters $A_r(G)=(1-r)\omega (G)+r\chi (G)$ for $0\le r\le 1$. It is proven that $A_r(k;K_n)\le n+\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ for small $r$. In addition, we prove some generalizations of a theorem of Kostochka, et al. \cite{kostochka}.