Covering line graphs with equivalence relations |
| |
Authors: | Louis Esperet John Gimbel |
| |
Institution: | a CNRS, Laboratoire G-SCOP, Grenoble, Franceb Mathematical Sciences, University of Alaska, Fairbanks, AK, USAc Department of Industrial Engineering and Operations Research, Columbia University, New York, NY, USA |
| |
Abstract: | An equivalence graph is a disjoint union of cliques, and the equivalence number 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: . This disproves a recent conjecture that is at most three for triangle-free G; indeed it can be arbitrarily large.To bound 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, . We prove that even when G is triangle-free, it is NP-complete to decide whether or not σ(G)≤3. |
| |
Keywords: | Equivalence covering Clique chromatic index Line graph Orientation covering Eyebrow number |
本文献已被 ScienceDirect 等数据库收录! |
|