Let be a family of sets ; then the intersection graph of is an undirected graph that has a vertex for each member of and an edge between each two members that have a nonempty intersection. Every graph can be represented as an intersection graph in this way. The intersection number of the graph is the smallest number such thatthere exists a representation of this type for which the union of has elements. The problem of finding an intersection representation of a graph with a given number of elements is known as the intersection graph basis problem.
Clique edge covers
An alternative definition of the intersection number of a graph is that it is the smallest number of cliques in that together cover all of the edges of. A set of cliques with this property is known as a clique edge cover or edge clique cover, and for this reason the intersection number is also sometimes called the edge clique cover number. The equality of the intersection number and the edge clique cover number is straightforward to prove. In one direction, suppose that is the intersection graph of a family of sets whose union has elements. Then for any element of, the subset of vertices of corresponding to sets that contain forms a clique: any two vertices in this subset are adjacent, because their sets have a nonempty intersection containing. Further, every edge in is contained in one of these cliques, because an edge corresponds to a nonempty intersection and an intersection is nonempty if it contains at least one element of. Therefore, the edges of can be covered by cliques, one per element of. In the other direction, if a graph can be covered by cliques, then each vertex of may be represented by the set of cliques that contain that vertex.
Upper bounds
Trivially, a graph with edges has intersection number at most, for each edge forms a clique and these cliques together cover all the edges. It is also true that every graph with vertices has intersection number at most. More strongly, the edges of every -vertex graph can be partitioned into at most cliques, all of which are either single edges or triangles. This generalizes Mantel's theorem that a triangle-free graph has at most edges, for in a triangle-free graph the only optimal clique edge cover has one clique per edge and therefore the intersection number equals the number of edges. An even tighter bound is possible when the number of edges is strictly greater than. Let p be the number of pairs of vertices that are not connected by an edge in the given graph, and let be the unique integer for which. Then the intersection number of is at most. Graphs that are the complement of a sparse graph have small intersection numbers: the intersection number of any -vertex graph is at most, where is the base of the natural logarithm and d is the maximum degree of the complement graph of.
Computational complexity
Testing whether a given graph has intersection number at most a given number is NP-complete. Therefore, it is also NP-hard to compute the intersection number of a given graph. The problem of computing the intersection number is, however, fixed-parameter tractable: that is, there is a function such that, when the intersection number is, the time to compute it is at most the product of and a polynomial in n. This may be shown by observing that there are at most distinct closed neighborhoods in the graph – two vertices that belong to the same set of cliques have the same neighborhood – and that the graph formed by selecting one vertex per closed neighbood has the same intersection number as the original graph. Therefore, in polynomial time the input can be reduced to a smaller kernel with at most vertices; applying an exponential timebacktracking search procedure to this kernel leads to a function that is double exponential in . The double-exponential dependence on cannot be reduced to single exponential by a kernelization of polynomial size, unless the polynomial hierarchy collapses, and if the exponential time hypothesis is true then double-exponential dependence is necessary regardless of whether kernelization is used. More efficient algorithms are also known for certain special classes of graphs. The intersection number of an interval graph is always equal to its number of maximal cliques, which may be computed in polynomial time. More generally, in chordal graphs, the intersection number may be computed by an algorithm that considers the vertices in an elimination ordering of the graph and that, for each vertex, forms a clique for and its later neighbors whenever at least one of the edges incident to is not covered by any earlier clique.
