论文标题
具有较小核心学位的关键2类图表的过度
Overfullness of critical class 2 graphs with a small core degree
论文作者
论文摘要
让$ g $成为一个简单的图形，让$ n $，$δ（g）$和$χ'（g）$分别为$ g $的订单，最高学位和色度指数。如果$ | e（g）|/\ lfloor n/2 \ rfloor>δ（g）$，我们将称为$ g $ overfull，如果$ g $的每个适当的子级$ h $ for $χ'（h）<χ'（g）$，则至关重要。显然，如果$ g $被覆盖，则$χ'（g）=δ（g）+1 $。 $ g $的核心用$g_δ$表示，是其所有最高度顶点引起的$ g $的子图。希尔顿（Hilton）和赵（Zhao）猜想，对于任何关键的2类图形$ g $，带有$δ（g）\ ge 4 $，如果最多$g_δ$的最高度最多为两个，则$ g $是Overfull，这又提供$δ（g）> n/2 +1 +1 $。我们表明，对于任何关键的2类图形$ g $，如果最低$g_δ$的最低度最多为两个，而$δ（g）> n/2 +1 $，则$ g $是Overfull。
Let $G$ be a simple graph, and let $n$, $Δ(G)$ and $χ' (G)$ be the order, the maximum degree and the chromatic index of $G$, respectively. We call $G$ overfull if $|E(G)|/\lfloor n/2\rfloor > Δ(G)$, and critical if $χ'(H) < χ'(G)$ for every proper subgraph $H$ of $G$. Clearly, if $G$ is overfull then $χ'(G) = Δ(G)+1$. The core of $G$, denoted by $G_Δ$, is the subgraph of $G$ induced by all its maximum degree vertices. Hilton and Zhao conjectured that for any critical class 2 graph $G$ with $Δ(G) \ge 4$, if the maximum degree of $G_Δ$ is at most two, then $G$ is overfull, which in turn gives $Δ(G) > n/2 +1$. We show that for any critical class 2 graph $G$, if the minimum degree of $G_Δ$ is at most two and $Δ(G) > n/2 +1$, then $G$ is overfull.
