DOIAbstract
AbstractAn equivalence graph is a disjoint union of cliques, and the equivalence number 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: 13log2log2χ(G)<eq(L(G))≤2log2log2χ(G)+2. This disproves a recent conjecture that eq(L(G)) is at most three for triangle-free G; indeed it can be arbitrarily large.To bound eq(L(G)) we bound the closely related invariant σ(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, σ(G)=eq(L(G)). We prove that even when G is triangle-free...
Add to ORKG