Overfullness of edge‐critical graphs with small minimal core degree
Overfullness of edge‐critical graphs with small minimal core degree
复制标题
边缘过度充满——最小核心度较小的临界图
DOI：
10.1002/jgt.23069
复制
发表时间：
2023
影响因子：
0.9
通讯作者：
Shan, Songling
中科院分区：
文献类型：
--
作者：
Cao, Yan;Chen, Guantao;Jing, Guangming;Shan, Songling
Let G $G$ be a simple graph. Let Δ ( G ) ${\rm{\Delta }}(G)$ and χ ′ ( G ) $\chi ^{\prime} (G)$ be the maximum degree and the chromatic index of G $G$, respectively. We call G $G$overfullif ∣ E ( G ) ∣ ∕ ⌊ ∣ V ( G ) ∣ ∕ 2 ⌋ > Δ ( G ) $| E(G)| \unicode{x02215}\lfloor | V(G)| \unicode{x02215}2\rfloor \gt {\rm{\Delta }}(G)$, andcriticalif χ ′ ( H ) < χ ′ ( G ) $\chi ^{\prime} (H)\lt \chi ^{\prime} (G)$ for every proper subgraph H $H$ of G $G$. Clearly, if G $G$ is overfull then χ ′ ( G ) = Δ ( G ) + 1 $\chi ^{\prime} (G)={\rm{\Delta }}(G)+1$. Thecoreof G $G$, denoted by G Δ ${G}_{{\rm{\Delta }}}$, is the subgraph of G $G$ induced by all its maximum degree vertices. We believe that utilizing the core degree condition could be considered as an approach to attack the overfull conjecture. Along this direction, we in this paper show that for any integer k ≥ 2 $k\ge 2$, if G $G$ is critical with Δ ( G ) ≥ 2 3 n + 3 k 2 ${\rm{\Delta }}(G)\ge \frac{2}{3}n+\frac{3k}{2}$ and δ ( G Δ ) ≤ k $\delta ({G}_{{\rm{\Delta }}})\le k$, then G $G$ is overfull.
Let G $G$ be a simple graph. Let Δ ( G ) ${\rm{\Delta }}(G)$ and χ ′ ( G ) $\chi ^{\prime} (G)$ be the maximum degree and the chromatic index of G $G$, respectively. We call G $G$overfullif ∣ E ( G ) ∣ ∕ ⌊ ∣ V ( G ) ∣ ∕ 2 ⌋ > Δ ( G ) $| E(G)| \unicode{x02215}\lfloor | V(G)| \unicode{x02215}2\rfloor \gt {\rm{\Delta }}(G)$, andcriticalif χ ′ ( H ) < χ ′ ( G ) $\chi ^{\prime} (H)\lt \chi ^{\prime} (G)$ for every proper subgraph H $H$ of G $G$. Clearly, if G $G$ is overfull then χ ′ ( G ) = Δ ( G ) + 1 $\chi ^{\prime} (G)={\rm{\Delta }}(G)+1$. Thecoreof G $G$, denoted by G Δ ${G}_{{\rm{\Delta }}}$, is the subgraph of G $G$ induced by all its maximum degree vertices. We believe that utilizing the core degree condition could be considered as an approach to attack the overfull conjecture. Along this direction, we in this paper show that for any integer k ≥ 2 $k\ge 2$, if G $G$ is critical with Δ ( G ) ≥ 2 3 n + 3 k 2 ${\rm{\Delta }}(G)\ge \frac{2}{3}n+\frac{3k}{2}$ and δ ( G Δ ) ≤ k $\delta ({G}_{{\rm{\Delta }}})\le k$, then G $G$ is overfull.
核心度较小的临界 2 类图的过满
DOI：
10.1016/j.jctb.2022.04.006
发表时间：
2022
期刊：
Series B
影响因子：
--
作者：
Cao, Yan;Chen, Guantao;Shan, Songling
通讯作者：
Shan, Songling