边染色临界图独立数的新下界  

The lower limit of the independence number in edge chromatic critical graphs

作　　者：齐林明 赵伟良[1] 苗连英 QI Linming;ZHAO Weiliang;MIAO Lianying(Zhejiang Industry Polytechnic College,Shaoxing 312000,Zhejiang,China;School of Mathematics,China University of Mining and Technology,Xuzhou 221116,Jiangsu,China)

机构地区：[1]浙江工业职业技术学院,浙江绍兴312000 [2]中国矿业大学数学学院,江苏徐州221116

出　　处：《运筹学学报(中英文)》2025年第1期225-231,共7页Operations Research Transactions

基　　金：国家自然科学基金(No.11771443);浙江省教育厅2021年度高校访问学者“教师专业发展项目”(No.FX2021169)。

摘　　要：1968年,Vizing提出猜想:如果图G是Δ-临界图,则其独立数α(G)满足α(G)≤n/2。这一猜想至今仍未解决。本文对于不含2度点的最大度较小的临界图,证明当最大度Δ∈{3,4,5,6}时,独立数α(G)≤(7Δ-6)/(12Δ-6)|V|;当Δ∈{7,8,9}时,独立数α(G)≤(4Δ-3)/(7Δ-3)|V|。In 1968,Vizing conjectured for any edge chromatic critical graph G with maximum degreeΔand independence numberα(G),a(G)≤n/2.This conjecture is still open.In this paper,we proved that a(G)≤(7Δ-6)/(12Δ-6)|V|forΔ∈{3,4,5,6}andα(G)≤(4Δ-3)/(7Δ-3)|V|forΔ∈{7,8,9}.

关 键 词：边染色 临界图 独立数 

分 类 号：O157.5[理学—数学]