A characterization of triangular and lattice graphs (Q1288230)

A complete bipartite graph \(K_{m,n}\) is called an \(n\)-claw provided that \(m=1\) and \(n\geq 2\). A graph on the vertex set \(X\times Y\) is an \(m\times n\)-graph provided that \((x_1,y_1)\) is adjacent to \((x_2,y_2)\) if and only if \(x_1=x_2\) or \(y_1=y_2\). A triangular graph \(T(m)\) has unordered pairs of elements in \(X\) as vertices, and \(\{a,b\}\) is adjacent to \(\{c,d\}\) if and only if \(\{a,b\}\cap\{c,d\}\neq\varnothing\). A strongly regular graph with parameters \((27,16,10,8)\) is called a Schäfli graph. If every vertex of a graph \(G\) is replaced by a nonempty clique (i.e., a complete subgraph) and every edge of \(G\) is replaced by a corresponding complete bipartite graph, then the resulting graph is called a clique extension of \(G\). If vertices \(a\) and \(b\) lie at distance 2 then the subgraph on their common neighbors is called a \(\mu\)-graph. Theorem. Let a connected graph \(\Gamma\) have a 3-coclique but no 3-claw. If each \(\mu\)-graph in \(\Gamma\) has radius greater than 1, then \(\Gamma\) is a clique extension of one of the following graphs: an \(m\times n\)-graph, where \(m\geq 3\), \(n\geq 3\); a triangular graph \(T(n)\), where \(n\geq 6\); a Schäfli graph.