Originators: L. Esperet, J. Gimbel, A. King (presented by Andrew King - REGS 2011) $\def\Gb{\overline{G}}$ $\def\Kb{\overline{K}}$
Definitions: An equivalence graph is a disjoint union of complete graphs. A set of equivalence subgraphs whose union is a graph $G$ is an equivalence covering of $G$. The minimum size of an equivalence covering of $G$ is the equivalence covering number of $G$, denoted eq$(G)$. A product embedding of a graph encodes each vertex as an integer vector so that vertices are adjacent if and only if their codes differ in any position; also, the encoding must be injective. The product dimension of $G$, denoted pdim$(G)$, is the minimum number of dimensions in which $G$ has a product embedding.
Background: It is natural to express a binary relation $\sim$ over a set $A$ as a union of transitive subrelations. When $\sim$ is reflexive and symmetric, each subrelation is an equivalence relation, and the problem of covering the relation with few subrelations becomes that of finding the equivalence covering number of a graph.
The equivalence covering number was introduced by Duchet [D]. It is very closely related to the the product dimension, introduced by Lovász, Nešetřil, and Pultr [LNP]. A product embedding expresses $G$ as the intersection of complete multipartite graphs; their complements are equivalence graphs whose union is $\Gb$. Thus pdim$(G)$ is almost eq$(\Gb)$; the difference is that the requirement of an injective encoding may make pdim$(G)$ larger than eq$(\Gb)$ by $1$. In particular, eq$(K_n)=1$, but pdim$(\Kb_n)=2$.
A matching is an equivalence, so eq$(G)\le\chi'(G)$, and equality holds for triangle-free graphs, where every equivalence subgraph forms a matching. A basic lower bound on pdim$(\Gb)$ (or eq$(G)$) was proved in [LNP]. Alon [A] rediscovered this result and used it to prove bounds that are good for graphs whose complements are sparse.
Theorem: ([A]) Let $G$ be an $n$-vertex graph other than $K_n$. If $\Delta(\Gb)\le d$, then $\lg(n/d) \leq {\rm eq}(G) \le c_d\lg n$, where $c_d=2e^2(d+1)^2\lg e$. Furthermore, the upper bound is an upper bound on the minimum number of complete graphs whose union is $G$, which is at least eq$(G)$.
Comments: For line graphs, eq$(G)$ was bounded within a multiplicative factor by Esperet, Gimbel, and King [EGK]. For any graph $G$, they proved $$\tfrac 13\lg\lg\chi(G)\le {\rm eq}(L(G)) \le 2 \lg\lg\chi(G)+2.$$
More generally, is there a good bound on the equivalence covering number of claw-free graphs? Claw-free graphs include proper circular-arc graphs, which in turn include powers of cycles. The cycle-power $C_n^k$ consists of $n$ vertices arranged on a circle, with each vertex adjacent to the closet $k$ vertices in each direction. Any $k+1$ consecutive vertices form a clique, and eq$(C_n^k)=k+1$ when $k+1$ divides $n$. Always $2k$ is an upper bound. Although no sublinear upper bound construction is known, also no good general lower bound is known.
Problem 1: Determine the asymptotics of eq$(C_n^k)$. In particular, is the value unbounded for fixed $k$? Is there an upper bound that is sublinear in $k$?
Comments: The equivalence covering number of line graphs is of interest also for its relation to another covering parameter. The orientation covering number of $G$, denoted $\sigma(G)$, is the minimum size of a set $S$ of orientations of $G$ such that, for every vertex $v$ and every two edges incident to $v$, there is an orientation in $S$ that directs those two edges outward from $v$. In a single orientation of $G$, one can orient all edges incident to a fixed independent set outward from that set, so $\sigma(G)\le \chi(G)$.
By converting the edges leaving a given vertex of an orientation of $G$ into a clique in the line graph, one obtains $\sigma(G)\ge {\rm eq}(L(G))$, and equality holds when $G$ is triangle-free. For general graphs, it is known that ${\rm eq}(L(G))\le \sigma(G)\le 3{\rm eq}(L(G))$. Can the upper bound be improved?
Conjecture 2: For $G$ a graph, $\sigma(G)\le {\rm eq}(L(G))+1$.
References:
[A] Alon, N.; Covering graphs by the minimum number of equivalence relations.
Combinatorica 6 (1986), no. 3, 201-206.
[D] P. Duchet, Représentations, noyaux en theéorie des graphes et
hypergraphes. PhD thesis, Université Paris VI, 1979.
[EGK] Esperet, Louis; Gimbel, John; King, Andrew.
Covering line graphs with equivalence relations.
Discrete Appl. Math. 158 (2010), no. 17, 1902-1907.
[LNP] Lovász, L.; Nešetřil, J.; Pultr, A.
On a product dimension of graphs.
J. Combin. Theory Ser. B 29 (1980), no. 1, 47-67.