Covering line graphs with equivalence relations

DOI10.1016/J.DAM.2010.08.012MaRDI QIDQ608272zbMATH OpenOpenAlexFDO

Authors L. Esperet, Andrew D. King, John Gimbel

Publication date 25 November 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.3692

zbMATH Keywords

clique chromatic indexequivalence coveringeyebrow numberline graphorientation covering

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: An equivalence graph is a disjoint union of cliques, and the equivalence number $mathiteq(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: $frac13lo{g}_{2}lo{g}_{2}chi(G)<mathiteq(L(G))leq2lo{g}_{2}lo{g}_{2}chi(G)+2$. This disproves a recent conjecture that $mathiteq(L(G))$ is at most three for triangle-free $G$; indeed it can be arbitrarily large. To bound $mathiteq(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)=mathiteq(L(G))$. We prove that even when $G$ is triangle-free, it is NP-complete to decide whether or not $sigma(G)leq3$.

Recommendations

• The equivalence number of a line graph
• On the equivalence covering number of splitgraphs
• scientific article; zbMATH DE number 4023332
• Covering graphs by the minimum number of equivalence relations
• A simple lower bound on edge coverings by cliques

Cites work

• Chromatic number of Hasse diagrams, eyebrows and dimension
• Covering graphs by the minimum number of equivalence relations
• scientific article; zbMATH DE number 426339 (Why is no real title available?)
• Minimal scrambling sets of simple orders
• On the equivalence covering number of splitgraphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs

Cited in

(5)

• Covering graphs by the minimum number of equivalence relations
• A computational complexity comparative study of graph tessellation problems
• A note on the orientation covering number
• The equivalence number of a line graph
• Equiangular lines and covers of the complete graph

This page was built for publication: Covering line graphs with equivalence relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q608272)