A Note on the Coloring of a Certain Class of Graphs

Abstract

Let \(\Gamma_\ell\) be the union of \(n\) complete graphs \(A_1, A_2, \ldots, A_n\) of size \(n\) each such that \(|A_i \cap A_j| \leq \ell\) whenever \(i \neq j\). We prove that the chromatic number of \(\Gamma_\ell\) is bounded above by \((2n – 4)\ell + 1\).