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. 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. Equivalently, the intersection number is the smallest number of cliques needed to cover all of the edges of $G$ .^[1]^[2]

A set of cliques that cover all edges of a graph is called a clique edge cover^[3] or edge clique cover,^[4] or even just a clique cover, although the last term is ambiguous: a clique cover can also be a set of cliques that cover all vertices of a graph.^[5] Sometimes "covering" is used in place of "cover".^[6] As well as being called the intersection number, the minimum number of these cliques has been called the R-content,^[7] edge clique cover number,^[4] or clique cover number.^[8] The problem of computing the intersection number has been called the intersection number problem,^[9] the intersection graph basis problem,^[10] covering by cliques,^[10] the edge clique cover problem,^[9] and the keyword conflict problem.^[2]

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

^ Cite error: The named reference gy06 was invoked but never defined (see the help page).
^ ^a ^b Cite error: The named reference r85 was invoked but never defined (see the help page).
^ Cite error: The named reference sv04 was invoked but never defined (see the help page).
^ ^a ^b Cite error: The named reference mtq06 was invoked but never defined (see the help page).
^ Cite error: The named reference gghn09 was invoked but never defined (see the help page).
^ Cite error: The named reference a86 was invoked but never defined (see the help page).
^ Cite error: The named reference o77 was invoked but never defined (see the help page).
^ Cite error: The named reference jh19 was invoked but never defined (see the help page).
^ ^a ^b Cite error: The named reference rs07 was invoked but never defined (see the help page).
^ ^a ^b Cite error: The named reference gj79 was invoked but never defined (see the help page).

[gy06-1] Cite error: The named reference gy06 was invoked but never defined (see the help page).

[r85-2] Cite error: The named reference r85 was invoked but never defined (see the help page).

[sv04-3] Cite error: The named reference sv04 was invoked but never defined (see the help page).

[mtq06-4] Cite error: The named reference mtq06 was invoked but never defined (see the help page).

[gghn09-5] Cite error: The named reference gghn09 was invoked but never defined (see the help page).

[a86-6] Cite error: The named reference a86 was invoked but never defined (see the help page).

[o77-7] Cite error: The named reference o77 was invoked but never defined (see the help page).

[jh19-8] Cite error: The named reference jh19 was invoked but never defined (see the help page).

[rs07-9] Cite error: The named reference rs07 was invoked but never defined (see the help page).

[gj79-10] Cite error: The named reference gj79 was invoked but never defined (see the help page).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]