Covering line graphs with equivalence relations

Details Covering line graphs with equivalence relations Covering line graphs with equivalence relations

2010-06-18

arxiv.org/abs/1006.3692v1

Discrete Applied Math., 158(17) (2010), 1902-1907

Mathematics

Combinatorics

10 pages, submitted in July 2009

Scientific paper

10.1016/j.dam.2010.08.012

An equivalence graph is a disjoint union of cliques, and the equivalence number $\mathit{eq}(G)$ of a graph $G$ is the minimum number of equivalence subgraphs needed to cover the edges of $G$. We consider the equivalence number of a line graph, giving improved upper and lower bounds: $\frac 13 \log_2\log_2 \chi(G) < \mathit{eq}(L(G)) \leq 2\log_2\log_2 \chi(G) + 2$. This disproves a recent conjecture that $\mathit{eq}(L(G))$ is at most three for triangle-free $G$; indeed it can be arbitrarily large. To bound $\mathit{eq}(L(G))$ we bound the closely-related invariant $\sigma(G)$, which is the minimum number of orientations of $G$ such that for any two edges $e,f$ incident to some vertex $v$, both $e$ and $f$ are oriented out of $v$ in some orientation. When $G$ is triangle-free, $\sigma(G)=\mathit{eq}(L(G))$. We prove that even when $G$ is triangle-free, it is NP-complete to decide whether or not $\sigma(G)\leq 3$.

Affiliated with

Also associated with

No associations

Rating

Covering line graphs with equivalence relations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Covering line graphs with equivalence relations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Covering line graphs with equivalence relations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-260621