Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420228 | Discrete Applied Mathematics | 2010 | 6 Pages |
Abstract
An equivalence graph is a disjoint union of cliques, and the equivalence number eq(G) of a graph GG is the minimum number of equivalence subgraphs needed to cover the edges of GG. We consider the equivalence number of a line graph, giving improved upper and lower bounds: 13log2log2χ(G)
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Louis Esperet, John Gimbel, Andrew King,