Intersection number (graph theory)

Summary

In the mathematical field of graph theory, the intersection number of a graph $G=(V,E)$ is the smallest number of elements needed to represent $G$ as an intersection graph of finite sets. In such a representation, each vertex is represented as a set, and two vertices are connected by an edge whenever their sets have a common element. The intersection number equals the smallest number of cliques (subgraphs with edges between all pairs of vertices) needed to cover all of the edges of $G$. Both this number and the computational problem of finding it have been studied under many alternative names.