Locally \(C_6\) graphs are clique divergent (Q1974531)

The clique graph \(kG\) of a graph \(G\) is the intersection graph of the family of all maximal complete subgraphs of \(G\). The iterated clique graphs \(k^nG\) are defined by \(k^0G= G\) and \(k^{n+1}G= kk^nG\). A graph \(G\) is said to be \(k\)-divergent if \(|V(k^nG)|\) tends to infinity with \(n\). A graph is locally \(C_6\) if the neighbours of any given vertex induce an hexagon. The authors prove that all locally \(C_6\) graphs are \(k\)-divergent and the diameters of the iterated clique graphs also tend to infinity with \(n\) while the sizes of the cliques remain bounded.