A Simple Algorithm for Coloring m-Clique Holes

An m-clique hole is a sequence $\varphi =({\mathrm{\Phi }}_1,{\mathrm{\Phi }}_2,\dots ,{\mathrm{\Phi }}_m)$ of $m$ distinct cliques such that $\mathrm{\mid }{\mathrm{\Phi }}_i\mathrm{\mid }\le m$ for all $i=1,2,\dots ,m$, and whose clique graph is a hole on $m$ vertices. That is, $\varphi$ is an m-clique hole if for all $i\mathrm{\ne }j$, $i,j=1,2,\dots ,m$, $\Phi_i \cap \Phi_{j} \neq \emptyset$ifandonlyif$(j-1)~\mbox{mod}~m = (j+1)~\mbox{mod}~m = i~\mbox{mod}~m$. This paper derives a sufficient and necessary condition on m-colorability of m-clique holes, and proposes a coloring algorithm that colors m-clique holes with exactly m colors.