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.