Intersection number (graph theory)

In the mathematical field of graph theory, the intersection number of a graph G = (V,E) is the smallest number of elements in a representation of G as an intersection graph of finite sets. Equivalently, it is the smallest number of cliques needed to cover all of the edges of G. In the mathematical field of graph theory, the intersection number of a graph G = (V,E) is the smallest number of elements in a representation of G as an intersection graph of finite sets. Equivalently, it is the smallest number of cliques needed to cover all of the edges of G. Let F be a family of sets (allowing sets in F to be repeated); then the intersection graph of F is an undirected graph that has a vertex for each member of F 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 k such that there exists a representation of this type for which the union of F has k 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. An alternative definition of the intersection number of a graph G is that it is the smallest number of cliques in G (complete subgraphs of G) that together cover all of the edges of G. 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 G is the intersection graph of a family F of sets whose union U has k elements. Then for any element x of U, the subset of vertices of G corresponding to sets that contain x forms a clique: any two vertices in this subset are adjacent, because their sets have a nonempty intersection containing x. Further, every edge in G 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 U. Therefore, the edges of G can be covered by k cliques, one per element of U. In the other direction, if a graph G can be covered by k cliques, then each vertex of G may be represented by the set of cliques that contain that vertex. Trivially, a graph with m edges has intersection number at most m, for each edge forms a clique and these cliques together cover all the edges. It is also true that every graph with n vertices has intersection number at most n2/4. More strongly, the edges of every n-vertex graph can be partitioned into at most n2/4 cliques, all of which are either single edges or triangles. This generalizes Mantel's theorem that a triangle-free graph has at most n2/4 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 n2/4. Let p be the number of pairs of vertices that are not connected by an edge in the given graph G, and let t be the unique integer for which t(t − 1) ≤ p < t(t + 1). Then the intersection number of G is at most p + t. Graphs that are the complement of a sparse graph have small intersection numbers: the intersection number of any n-vertex graph G is at most 2e2(d + 1)2ln n, where e is the base of the natural logarithm and d is the maximum degree of the complement graph of G. Testing whether a given graph G has intersection number at most a given number k is NP-complete. Therefore, it is also NP-hard to compute the intersection number of a given graph.