Intersection number (graph theory)

In the mathematical field of graph theory, the intersection number of a graph ${\displaystyle G=(V,E)}$ is the smallest number of elements needed to represent ${\displaystyle 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 ${\displaystyle G}$. Both this number and the computational problem of finding it have been studied under many alternative names.

Applications of the intersection number include scheduling users of a shared resource or operations on very long instruction word computers, bandwidth allocation in fiber optic networks, data visualization using compact letter displays, the analysis of food webs in biology, and the inference of protein complexes from protein–protein interaction networks.

Every graph with ${\displaystyle n}$ vertices and ${\displaystyle m}$ edges has intersection number at most ${\displaystyle \min(m,n^{2}/4)}$. The intersection number is NP-hard to compute or approximate, but fixed-parameter tractable.