Covering line graphs with equivalence relations
Covering line graphs with equivalence relations
复制标题
用等价关系覆盖线图
DOI：
10.1016/j.dam.2010.08.012
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Andrew D. King
中科院分区：
文献类型：
--
作者：
Louis Esperet;J. Gimbel;Andrew D. King
等价图是团的不相交并，图G的等价数eq(G)是覆盖G的边所需的等价子图的最小个数。我们考虑线图的等价数，给出了改进的上下界：13log2log2χ(G)<；eq(L(G))≤2log2log2χ(G)+2。这证明了最近的一个猜想：对于无三角形的G，eq(L(G))至多为3；事实上，它可以是任意大的。为了给Eq(L(G))定界，我们定义了密切相关的不变量σ(G)，它是G的最小方向数，使得对于任意两条与某个顶点v相交的边e，f，e和f都在v的某个方向上定向。当G无三角形时，σ(G)=eq(L(G))。我们证明了即使当G是无三角形的时，决定是否σ(G)≤3也是NP完全的。
An 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, it is NP-complete to decide whether or not σ(G)≤3.