Completely Independent Critical Cliques

Abstract

If $K$ is an $r$-clique of $G$ and $\chi (G)$ decreases by $r$ upon the removal of all of the vertices in $K$, then $K$ is called a critical $r$-clique. Two critical cliques are completely independent provided that no vertex in one clique is adjacent to a vertex from the other. An infinite family of graphs is constructed which demonstrates that for every $s,t\in \mathbb{N}$, there exists a vertex critical graph which admits a critical $s$-clique and a critical $t$-clique that are completely independent.