Independence number of edge‐chromatic critical graphs
Independence number of edge‐chromatic critical graphs
复制标题
边独立数－色临界图
DOI：
10.1002/jgt.22825
复制
发表时间：
2022
影响因子：
0.9
通讯作者：
Shan, Songling
中科院分区：
文献类型：
--
作者：
Cao, Yan;Chen, Guantao;Jing, Guangming;Shan, Songling
设G G是一个简单图，其最大度为Δ（G）Δ（G），色指数为χ′（G）χ^′（G）. Vizing的一个经典结果表明，要么χ′（G）= Δ（G）χ^′（G）=Δ（G），要么χ′（G）= Δ（G）+1 χ^′（G）=Δ（G）+1.一个简单图G称为边-Δ Δ-临界图，如果G是连通的，且对任意e∈ E（G）e∈E（G），χ ′（G）=Δ（G）+ 1 χ^′（G）= Δ（G）+1.设G G是一个n n-顶点边-Δ Δ-临界图. Vizing证明了G的独立数α（G）α（G）至多为n2 n2. Woodall给出的关于这个猜想的最好结果是α（G）< 3 n5 α（G）\lt3n5。证明了对任意给定的ε∈（0，1）ε∈（0，1），存在正的常数d 0（ε）d 0（ε）和D 0（ε）D 0（ε），使得如果G是一个n-顶点边-Δ Δ-临界图，最小度至少为d 0 d 0，最大度至少为D 0 D 0，则α（G）<12 + ε n α（G）\lt\left（12+ε\right）n.特别地，我们证明了：若G是n n-顶点边-Δ Δ-临界图，且最小度至少为d d，且Δ（G）≥（d+ 1）4.5d + 11.5 Δ（G）≥（d+1）^4.5d+11.5，则α（G）< 7 n12，如果d= 3，则α（G）<4 n7，如果d= 4，d+ 2+（d− 1）d 3 2 d+ 4+（d− 1）d 3 n< 4 n 7 if d≥ 19.α（G）\lt\left.左{\displaystyle 7n12 &\，if\，\，d = 3，\4n7 &\，if\，\，d = 4，\d +2+\sqrt3（d-1）d2d+4+\sqrt3（d-1）dn\lt4n7 &\，if\，\，d ≥19..
Let G G be a simple graph with maximum degree Δ (G) Δ(G) and chromatic index χ′(G) χ^′(G). A classical result of Vizing shows that either χ′(G)= Δ (G) χ^′(G)=Δ(G) or χ′(G)= Δ (G)+ 1 χ^′(G)=Δ(G)+1. A simple graph G G is called edge‐Δ Δ‐critical if G G is connected, χ′(G)= Δ (G)+ 1 χ^′(G)=Δ(G)+1 and χ′(G− e)= Δ (G) χ^′(Ge)=Δ(G) for every e∈ E (G) e∈E(G). Let G G be an n n‐vertex edge‐Δ Δ‐critical graph. Vizing conjectured that α (G) α(G), the independence number of G G, is at most n 2 n2. The current best result on this conjecture, shown by Woodall, is α (G)< 3 n 5 α(G)\lt3n5. We show that for any given ε∈(0, 1) ε∈(0,1), there exist positive constants d 0 (ε) d_0(ε) and D 0 (ε) D_0(ε) such that if G G is an n n‐vertex edge‐Δ Δ‐critical graph with minimum degree at least d 0 d_0 and maximum degree at least D 0 D_0, then α (G)< 1 2+ ε n α(G)\lt\left(12+ε\right)n. In particular, we show that if G G is an n n‐vertex edge‐Δ Δ‐critical graph with minimum degree at least d d and Δ (G)≥(d+ 1) 4.5 d+ 11.5 Δ(G)≥(d+1)^4.5d+11.5, then α (G)< 7 n 12 if d= 3, 4 n 7 if d= 4, d+ 2+(d− 1) d 3 2 d+ 4+(d− 1) d 3 n< 4 n 7 if d≥ 19. α(G)\lt\left.\left{\displaystyle7n12&\,if\,\,d=3,\4n7&\,if\,\,d=4,\d+2+\sqrt3(d-1)d2d+4+\sqrt3(d-1)dn\lt4n7&\,if\,\,d≥19..