Edge coloring graphs with large minimum degree
Edge coloring graphs with large minimum degree
复制标题
最小度数较大的边着色图
DOI：
10.1002/jgt.22889
复制
发表时间：
2023
影响因子：
0.9
通讯作者：
Shan, Songling
中科院分区：
文献类型：
--
作者：
Plantholt, Michael J.;Shan, Songling
Let G $G$ be a simple graph with maximum degree Δ ( G ) ${\rm{\Delta }}(G)$. A subgraph H $H$ of G $G$ is overfull if ∣ E ( H ) ∣ > Δ ( G ) ⌊ ∣ V ( H ) ∣ ∕ 2 ⌋ . $| E(H)| \gt {\rm{\Delta }}(G)\lfloor | V(H)| \unicode{x02215}2\rfloor .$ Chetwynd and Hilton in 1986 conjectured that a graph G $G$ with Δ ( G ) > ∣ V ( G ) ∣ ∕ 3 ${\rm{\Delta }}(G)\gt | V(G)| \unicode{x02215}3$ has chromatic index Δ ( G ) ${\rm{\Delta }}(G)$ if and only if G $G$ contains no overfull subgraph. The best previous results supporting this conjecture have been obtained for regular graphs. For example, Perković and Reed verified the conjecture for large regular graphs G $G$ with degree arbitrarily close to ∣ V ( G ) ∣ ∕ 2 $| V(G)| \unicode{x02215}2$. We provide a similar result for general graphs asymptotically, showing that for any given 0 < ϵ < 1 $0\lt \epsilon \lt 1$, there exists a positive integer n 0 ${n}_{0}$ such that the following statement holds: if G $G$ is a graph on 2 n ≥ n 0 $2n\ge {n}_{0}$ vertices with minimum degree at least ( 1 + ϵ ) n $(1+\epsilon )n$, then G $G$ has chromatic index Δ ( G ) ${\rm{\Delta }}(G)$ if and only if G $G$ contains no overfull subgraph.
Let G $G$ be a simple graph with maximum degree Δ ( G ) ${\rm{\Delta }}(G)$. A subgraph H $H$ of G $G$ is overfull if ∣ E ( H ) ∣ > Δ ( G ) ⌊ ∣ V ( H ) ∣ ∕ 2 ⌋ . $| E(H)| \gt {\rm{\Delta }}(G)\lfloor | V(H)| \unicode{x02215}2\rfloor .$ Chetwynd and Hilton in 1986 conjectured that a graph G $G$ with Δ ( G ) > ∣ V ( G ) ∣ ∕ 3 ${\rm{\Delta }}(G)\gt | V(G)| \unicode{x02215}3$ has chromatic index Δ ( G ) ${\rm{\Delta }}(G)$ if and only if G $G$ contains no overfull subgraph. The best previous results supporting this conjecture have been obtained for regular graphs. For example, Perković and Reed verified the conjecture for large regular graphs G $G$ with degree arbitrarily close to ∣ V ( G ) ∣ ∕ 2 $| V(G)| \unicode{x02215}2$. We provide a similar result for general graphs asymptotically, showing that for any given 0 < ϵ < 1 $0\lt \epsilon \lt 1$, there exists a positive integer n 0 ${n}_{0}$ such that the following statement holds: if G $G$ is a graph on 2 n ≥ n 0 $2n\ge {n}_{0}$ vertices with minimum degree at least ( 1 + ϵ ) n $(1+\epsilon )n$, then G $G$ has chromatic index Δ ( G ) ${\rm{\Delta }}(G)$ if and only if G $G$ contains no overfull subgraph.
登录
查看更多内容
汉密尔顿自行车
DOI：
--
发表时间：
2021
期刊：
The Discrete Mathematical Charms of Paul Erdős
影响因子：
--
作者：
Frank de Zeeuw
通讯作者：
Frank de Zeeuw
具有高最小度的图的过满猜想
影响因子：
0.9
作者：
M. Plantholt
通讯作者：
M. Plantholt
如何在最大度数较大的图中查找满子图，II
影响因子：
0.7
作者：
T. Niessen
通讯作者：
T. Niessen
影响因子：
0.9
作者：
E. Vaughan
通讯作者：
E. Vaughan
偶数阶 n 大且最小度至少为 2n/3 的图的色指数
影响因子：
0.8
作者：
M. Plantholt
通讯作者：
M. Plantholt