Hamiltonicity of edge-chromatic critical graphs
Hamiltonicity of edge-chromatic critical graphs
复制标题
边色临界图的哈密顿度
DOI：
10.1016/j.disc.2020.111881
复制
发表时间：
2020
影响因子：
0.8
通讯作者：
Fuliang Lu
中科院分区：
文献类型：
--
作者：
Yan Cao;Guantao Chen;Suyun Jiang;Huiqing Liu;Fuliang Lu
给定一个图G，用Δ（G）和χ′（G）分别表示G的最大度和色指数.简单图G称为边-Δ-临界图，如果对G的每个真子图H，Δ（G）= Δ，χ′（G）= Δ+ 1且χ′（H）≤ Δ.证明了最大度至少为2n 3+ 12的n阶边-Δ-临界图是Hamilton图.
Given a graph G, denote by Δ (G) and χ′(G) the maximum degree and the chromatic index of G, respectively. A simple graph G is called edge-Δ-critical if Δ (G)= Δ, χ′(G)= Δ+ 1 and χ′(H)≤ Δ for every proper subgraph H of G. We prove that every edge-Δ-critical graph of order n with maximum degree at least 2 n 3+ 12 is Hamiltonian.