Overfull conjecture for graphs with high minimum degree
Overfull conjecture for graphs with high minimum degree
复制标题
具有高最小度的图的过满猜想
作者：
M. Plantholt
Chetwynd和希尔顿证明了任意偶数阶n正则图G具有相对高的度$Delta（G），ge，（（sqrt{7}- 1）/2），n$，都有1-因子分解。这相当于说，在这些条件下，G的色指数等于它的最大度$Delta（G）$。利用这一结果，我们证明了任何偶数阶n的图G（不一定是正则的），只要G不包含一个“过满”子图，即一个平凡地迫使其色指数大于最大度的子图，则G具有足够高的最小度$delta（G），ge，（sqrt{7}/3），n$，其色指数等于其最大度。这一结果证明了偶阶图的过满猜想和足够高的最小度。© 2004 Wiley Periodicals，Inc. J Graph Theory 47：73-80，2004
Chetwynd and Hilton showed that any regular graph G of even order n which has relatively high degree $Delta (G),ge,((sqrt{7}- 1)/2), n$ has a 1‐factorization. This is equivalent to saying that under these conditions G has chromatic index equal to its maximum degree $Delta(G)$. Using this result, we show that any (not necessarily regular) graph G of even order n that has sufficiently high minimum degree $delta(G),ge,(sqrt{7}/3),n$ has chromatic index equal to its maximum degree providing that G does not contain an “overfull” subgraph, that is, a subgraph which trivially forces the chromatic index to be more than the maximum degree. This result thus verifies the Overfull Conjecture for graphs of even order and sufficiently high minimum degree. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 73–80, 2004