Sphericity, cubicity, and edge clique covers of graphs (Q2495913): Difference between revisions

The sphericity \(\text{sph}(G)\) of a graph \(G\) is the minimum dimension \(d\) for which \(G\) is the intersection graph of a family of congruent spheres in \textbf{R}\(^d\). The edge clique cover number \(\theta(G)\) of a graph \(G\) is the minimum cardinality of a set of cliques that contains all edges of \(G\). If \(G\) is a graph with \(\theta(G)\geq 1\), then the authors prove that \(\text{sph}(G)\leq\theta(G)\). This bound remains valid for intersection graphs defined by balls in the \(L_p\)-norm for \(1\leq p\leq\infty\).