Covering line graphs with equivalence relations ?
An equivalence graph is a disjoint union of cliques, and the equivalence number eq ( G ) of a graph G G is the minimum number of equivalence subgraphs needed to cover the edges of G G . We consider the equivalence number of a line graph, giving improved upper and lower bounds: 1 3 log 2 log 2 ? ( G ) < eq ( L ( G ) ) ? 2 log 2 log 2 ? ( G ) + 2 . This disproves a recent conjecture that eq ( L ( G ) ) is at most three for triangle-free G G ; indeed it can be arbitrarily large. To bound eq ( L ( G ) ) we bound the closely related invariant ?(G) ? ( G ) , which is the minimum number of orientations of G G such that for any two edges e,f e , f incident to some vertex v v , both e e and f f are oriented out of v v in some orientation. When G G is triangle-free, ? ( G ) = eq ( L ( G ) ) . We prove that even when G G is triangle-free, it is NP-complete to decide whether or not ?(G)?3 ? ( G ) ? 3 .
line graph equivalence covering clique chromatic index orientation covering eyebrow number