Covering powers of cycles with equivalence subgraphs

Importance: Low ✭
Subject: Graph Theory
Recomm. for undergrads: no
Posted by: Andrew King
on: July 7th, 2011

\begin{conjecture} Given $k$ and $n$, the graph $C_{n}^k$ has equivalence covering number $\Omega(k)$. \end{conjecture}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{} Given a graph $G$, a subgraph $H$ of $G$ is an \emph{equivalence subgraph of $G$} if $H$ a disjoint union of cliques. The \emph{quivalence covering number} of $G$, denoted $eq(G)$, is the least number of equivalence subgraphs needed to cover the edges of $G$.

This problem has been studied by various people since the 80s [A]. For line graphs, the equivalence covering number is known to within a constant factor [EGK]. It is therefore tempting to examine the situation for quasi-line graphs and claw-free graphs. Powers of cycles are perhaps the simplest interesting class of claw-free graphs that are not necessarily line graphs. However, even for $n$ very large compared to $k$, no upper bound is known beyond trivial linear bounds of order $\Theta(k)$. Furthermore, it is not even certain that a nontrivial lower bound (i.e. going to infinity as $k$ goes to infinity) is known. It is possible that this can be related somehow to a known result, but for now it seems at least superficially that this problem is wide open.


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

[A] N. Alon, Covering graphs with the minimum number of equivalence relations, Combinatorica 6 (1986) 201–206.

[EGK] L. Esperet, J. Gimbel, A. King, Covering line graphs with equivalence relations, Discrete Applied Mathematics Volume 158, Issue 17, 28 October 2010, Pages 1902-1907.

* indicates original appearance(s) of problem.