How to Find Overfull Subgraphs in Graphs with Large Maximum Degree, II
How to Find Overfull Subgraphs in Graphs with Large Maximum Degree, II
复制标题
如何在最大度数较大的图中查找满子图，II
DOI：
--
复制
发表时间：
2000
影响因子：
0.7
通讯作者：
T. Niessen
中科院分区：
文献类型：
--
作者：
T. Niessen
设$G$是一个简单图，其中$3Delta（G）>| V| $.过满图猜想指出，如果$G$不包含满足$Delta（H）= Delta（G）$的导出过满子图$H$，则$G$的色指数等于$Delta（G）$，否则它等于$Delta（G）+1 $。我们提出了一个算法，确定这些子图在$O（n^{5/3}m）$的时间，在一般情况下，在$O（n^3）$的时间，如果$G$是正则的。此外，它表明，$G$可以有最多三个这些子图。如果$2Delta（G）geq| V| $，则$G$最多包含其中一个子图，并且我们以前的算法针对这种情况进行了改进，使其在线性时间内运行。
Let $G$ be a simple graph with $3Delta (G) > |V|$. The Overfull Graph Conjecture states that the chromatic index of $G$ is equal to $Delta (G)$, if $G$ does not contain an induced overfull subgraph $H$ with $Delta (H) = Delta (G)$, and otherwise it is equal to $Delta (G) +1$. We present an algorithm that determines these subgraphs in $O(n^{5/3}m)$ time, in general, and in $O(n^3)$ time, if $G$ is regular. Moreover, it is shown that $G$ can have at most three of these subgraphs. If $2Delta (G) geq |V|$, then $G$ contains at most one of these subgraphs, and our former algorithm for this situation is improved to run in linear time.