论文标题
$Δ$ - 至关格2的顶点
$Δ$-critical graphs with a vertex of degree 2
论文作者
论文摘要
令$ g $为最大程度$δ$的简单图。 Vibe的经典结果表明，$ g $的色度指数$χ'（g）$是$δ$或$δ+1 $。我们说$ g $是\ emph {class 1}如果$χ'（g）=δ$，并且否则为\ emph {class 2}。图$ g $是\ emph {$δ$ -Critical}如果$χ'（g）=δ+1 $和$χ'和$χ'（h）<δ+1 $对于$ g $的每个适当的子图$ h $，并且IS \ emph {overfull}如果$ | e（g）显然，Overfull图是2级。Hilton和Zhao在1997年猜想，如果$ g $是从$ n $ n $ vertex $ vertex $Δ$δ$δ$ - 最高学位的1级图表中，则通过拆分$ n/3 $，通过拆分$ n/3 $，那么被覆盖是$ g $的唯一原因。 \ frac {n} {2}（\ sqrt {7} -1）\大约0.82n $。在本文中，我们从$ \ frac {n} {2}（\ sqrt {7} -1）$从$ \ frac {n} {2}提高了$δ$的绑定。考虑到$δ$ - 临界图的结构，其顶点为2度，我们还表明，对于$ n $ vertex $δ$ - 关键图，带有$δ\ ge \ ge \ frac {3n} {4} $，如果它包含了2度的顶点2的顶点，则是覆盖的。实际上，我们获得了这种结果的更一般形式，从1986年开始，该结果部分支持了Chetwynd和Hilton的过失猜想，该猜测是，如果$ g $是$ n $ n $ vertex $δ$ - $Δ> n/3 $，则$ g $ g $，则$ g，则$ g，则包含Overfull $ h $ H $ a $ h $ a $ h $ a $ g $Δ$Δ（H）=Δ$Δ=δ=δ=Δ$Δ=δ=Δ$δ=δ我们的证明技术是新的，当$δ$很大时，可能会阐明攻击这两种猜想。
Let $G$ be a simple graph with maximum degree $Δ$. A classic result of Vizing shows that $χ'(G)$, the chromatic index of $G$, is either $Δ$ or $Δ+1$. We say $G$ is of \emph{Class 1} if $χ'(G)=Δ$, and is of \emph{Class 2} otherwise. A graph $G$ is \emph{$Δ$-critical} if $χ'(G)=Δ+1$ and $χ'(H)<Δ+1$ for every proper subgraph $H$ of $G$, and is \emph{overfull} if $|E(G)|>Δ\lfloor (|V(G)|-1)/2 \rfloor$. Clearly, overfull graphs are Class 2. Hilton and Zhao in 1997 conjectured that if $G$ is obtained from an $n$-vertex $Δ$-regular Class 1 graph with maximum degree greater than $n/3$ by splitting a vertex, then being overfull is the only reason for $G$ to be Class 2. This conjecture was only confirmed when $Δ\ge \frac{n}{2}(\sqrt{7}-1)\approx 0.82n$. In this paper, we improve the bound on $Δ$ from $\frac{n}{2}(\sqrt{7}-1)$ to $0.75n$. Considering the structure of $Δ$-critical graphs with a vertex of degree 2, we also show that for an $n$-vertex $Δ$-critical graph with $Δ\ge \frac{3n}{4}$, if it contains a vertex of degree 2, then it is overfull. We actually obtain a more general form of this result, which partially supports the overfull conjecture of Chetwynd and Hilton from 1986, which states that if $G$ is an $n$-vertex $Δ$-critical graph with $Δ>n/3$, then $G$ contains an overfull subgraph $H$ with $Δ(H)=Δ$. Our proof techniques are new and might shed some light on attacking both of the conjectures when $Δ$ is large.
