INDUCED MATCHINGS IN CUBIC GRAPHS
INDUCED MATCHINGS IN CUBIC GRAPHS
复制标题
DOI：
10.1002/jgt.3190170204
复制
发表时间：
1993-06-01
影响因子：
0.9
通讯作者：
TROTTER, WT
中科院分区：
文献类型：
--
作者：
HORAK, P;QING, H;TROTTER, WT
在本文中，我们证明了一个三次图的边集总是可以划分成10个子集，每一个子集诱导图中的一个匹配。这个结果是Erdos和Nesetril的一个一般猜想的特殊情况：对于每个d ≥ 3，最大度d的图的边集总是可以划分为右垂直的5d ~ 2/4个左垂直子集，每个子集都诱导一个匹配。
In this paper, we show that the edge set of a cubic graph can always be partitioned into 10 subsets, each of which induces a matching in the graph. This result is a special case of a general conjecture made by Erdos and Nesetril: For each d greater-than-or-equal-to 3, the edge set of a graph of maximum degree d can always be partitioned into right perpendicular 5d2/4 left perpendicular subsets each of which induces a matching.