论文标题
希尔顿和赵的核心猜想的证明
Proof of the Core Conjecture of Hilton and Zhao
论文作者
论文摘要
令$ g $为最大程度$δ$的简单图。如果$ | e（g）|>δ\ lfloor | v（g）|/2 \ rfloor $，我们称$ g $ \ emph {overfull}。 $ g $的\ emph {core}，表示为$g_δ$，是其$δ$的顶点引起的$ g $的子图。 Vibe的经典结果表明，$ g $的色度指数$χ'（g）$是$δ$或$δ+1 $。确定一般图的色度索引是NP完整的。但是，如果$ g $被覆盖，则$χ'（g）=δ+1 $。 Hilton and Zhao in 1996 conjectured that if $G$ is a simple connected graph with $Δ\ge 3$ and $Δ(G_Δ)\le 2$, then $χ'(G)=Δ+1$ if and only if $G$ is overfull or $G=P^*$, where $P^*$ is obtained from the Petersen graph by deleting a vertex.该猜想（如果为true）意味着一种简单的方法来计算满足条件的图形$ g $的$χ'（g）$。猜想的进展很慢：它仅在2003年和2017年才以$δ= 3,4 $确认。在本文中，我们确认了所有$δ\ ge 4 $的猜想。
Let $G$ be a simple graph with maximum degree $Δ$. We call $G$ \emph{overfull} if $|E(G)|>Δ\lfloor |V(G)|/2\rfloor$. The \emph{core} of $G$, denoted $G_Δ$, is the subgraph of $G$ induced by its vertices of degree $Δ$. A classic result of Vizing shows that $χ'(G)$, the chromatic index of $G$, is either $Δ$ or $Δ+1$. It is NP-complete to determine the chromatic index for a general graph. However, if $G$ is overfull then $χ'(G)=Δ+1$. Hilton and Zhao in 1996 conjectured that if $G$ is a simple connected graph with $Δ\ge 3$ and $Δ(G_Δ)\le 2$, then $χ'(G)=Δ+1$ if and only if $G$ is overfull or $G=P^*$, where $P^*$ is obtained from the Petersen graph by deleting a vertex. This conjecture, if true, implies an easy approach for calculating $χ'(G)$ for graphs $G$ satisfying the conditions. The progress on the conjecture has been slow: it was only confirmed for $Δ=3,4$, respectively, in 2003 and 2017. In this paper, we confirm this conjecture for all $Δ\ge 4$.
