English

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (1): 225-231.doi: 10.15960/j.cnki.issn.1007-6093.2025.01.019

•   • 上一篇    下一篇

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

齐林明1,*(), 赵伟良1, 苗连英2   

  1. 1. 浙江工业职业技术学院, 浙江绍兴 312000
    2. 中国矿业大学数学学院, 江苏徐州 221116
  • 收稿日期:2021-10-21 出版日期:2025-03-15 发布日期:2025-03-08
  • 通讯作者: 齐林明 E-mail:qilinmingxr@163.com
  • 基金资助:
    国家自然科学基金(11771443);浙江省教育厅2021年度高校访问学者“教师专业发展项目”(FX2021169)

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

Linming QI1,*(), Weiliang ZHAO1, Lianying MIAO2   

  1. 1. Zhejiang Industry Polytechnic College, Shaoxing 312000, Zhejiang, China
    2. School of Mathematics and Science, Nanjing Normal University, Nanjing 210023, Jiangsu, China
  • Received:2021-10-21 Online:2025-03-15 Published:2025-03-08
  • Contact: Linming QI E-mail:qilinmingxr@163.com

RichHTML

0

PDF

28

摘要：

1968年，Vizing提出猜想:如果图$G$是$\Delta$-临界图, 则其独立数$\alpha (G)$满足$\alpha (G)\leqslant\dfrac{n}{2}$。这一猜想至今仍未解决。本文对于不含$度点的最大度较小的临界图, 证明当最大度$\Delta\in\{3, 4, 5, 6\}$时, 独立数$\alpha (G)\leqslant\dfrac{7\Delta-6}{12\Delta-6}|V|$;当$\Delta\in\{7, 8, 9\}$时, 独立数$\alpha (G)\leqslant\dfrac{4\Delta-3}{7\Delta-3}|V|$。

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

Abstract:

In 1968, Vizing conjectured for any edge chromatic critical graph $G$ with maximum degree $\Delta$ and independence number $\alpha(G)$, $\alpha(G)\leqslant\dfrac{n}{2}$. This conjecture is still open. In this paper, we proved that $\alpha(G)\leqslant\dfrac{7\Delta-6}{12\Delta-6}|V|$ for $\Delta\in\{3, 4, 5, 6\} $ and $\alpha(G)\leqslant \dfrac{4\Delta-3}{7\Delta-3}|V|$ for $\Delta\in\{7, 8, 9\}$.

Key words: edge coloring, critical graphs, independence number

中图分类号: