Overfullness of critical class 2 graphs with a small core degree
Overfullness of critical class 2 graphs with a small core degree
复制标题
核心度较小的临界 2 类图的过满
DOI：
10.1016/j.jctb.2022.04.006
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Shan, Songling
中科院分区：
文献类型：
--
作者：
Cao, Yan;Chen, Guantao;Shan, Songling
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)|/⌊ n/2⌋> Δ (G), and critical if χ′(H)< χ′(G) for every proper subgraph H of G. Clearly, if G is overfull then χ′(G)= Δ (G)+ 1 by Vizing's Theorem. 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)≥ 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.
具有高最小度的图的过满猜想
影响因子：
0.9
作者：
M. Plantholt
通讯作者：
M. Plantholt