Chromatic index of dense quasirandom graphs
Chromatic index of dense quasirandom graphs
复制标题
稠密拟随机图的色指数
DOI：
10.1016/j.jctb.2022.08.001
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Shan, Songling
中科院分区：
文献类型：
--
作者：
Shan, Songling
设G为最大次为Δ (G)的简单图。若子图H中有| E (H)|> Δ (G)⌊| V (H)|/2⌋，则表示子图H满。Chetwynd和Hilton（1986）推测，当且仅当G不包含过满子图时，具有Δ (G) b> n/3的n个顶点上的图G具有色指数Δ (G)。Glock, k<s:1> hn和Osthus（2016）证明了这个猜想对于偶数阶的密集准随机图是成立的，他们推测对于奇数阶的密集准随机图也是成立的。本文证明了格洛克、k<s:1> hn和Osthus的猜想是肯定的。
Let G be a simple graph with maximum degree Δ (G). A subgraph H of G is overfull if| E (H)|> Δ (G)⌊| V (H)|/2⌋. Chetwynd and Hilton in 1986 conjectured that a graph G on n vertices with Δ (G)> n/3 has chromatic index Δ (G) if and only if G contains no overfull subgraph. Glock, Kühn and Osthus in 2016 showed that the conjecture is true for dense quasirandom graphs with even order, and they conjectured that the same should hold for such graphs with odd order. In this paper, we show that the conjecture of Glock, Kühn and Osthus is affirmative.