A Note on the Coloring of a Certain Class of Graphs

Abstract

Let ${\mathrm{\Gamma }}_{\ell }$ be the union of $n$ complete graphs $A_1,A_2,\dots ,A_n$ of size $n$ each such that $|A_i\cap A_j|\le \ell$ whenever $i\ne j$. We prove that the chromatic number of ${\mathrm{\Gamma }}_{\ell }$ is bounded above by $(2n–4)\ell +1$.