Intersection graph

In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them.

Formal definition

Formally, an intersection graph G is an undirected graph formed from a family of sets

S

i

,

i

=

0

,

1

,

2

,

…

{\displaystyle S_{i},\,\,\,i=0,1,2,\dots }

by creating one vertex vi for each set Si, and connecting two vertices vi and vj by an edge whenever the corresponding two sets have a nonempty intersection, that is,

E

(

G

)

=

{

{

v

i

,

v

j

}

∣

i

≠

j

,

S

i

∩

S

j

≠

∅

}

.

{\displaystyle E(G)=\{\{v_{i},v_{j}\}\mid i\neq j,S_{i}\cap S_{j}\neq \emptyset \}.}

All graphs are intersection graphs

Any undirected graph G may be represented as an intersection graph. For each vertex vi of G, form a set Si consisting of the edges incident to vi; then two such sets have a nonempty intersection if and only if the corresponding vertices share an edge. Therefore, G is the intersection graph of the sets Si.

Erdős, Goodman & Pósa (1966) provide a construction that is more efficient, in the sense that it requires a smaller total number of elements in all of the sets Si combined. For it, the total number of set elements is at most ⁠n2/4⁠, where n is the number of vertices in the graph. They credit the observation that all graphs are intersection graphs to Szpilrajn-Marczewski (1945), but say to see also Čulík (1964). The intersection number of a graph is the minimum total number of elements in any intersection representation of the graph.