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

展开
  • 1. 浙江工业职业技术学院, 浙江绍兴 312000
    2. 中国矿业大学数学学院, 江苏徐州 221116
齐林明, E-mail:qilinmingxr@163.com

收稿日期: 2021-10-21

  网络出版日期: 2025-03-08

基金资助

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

版权

运筹学学报编辑部, 2025, 版权所有,未经授权,不得转载。

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

Expand
  • 1. Zhejiang Industry Polytechnic College, Shaoxing 312000, Zhejiang, China
    2. School of Mathematics and Science, Nanjing Normal University, Nanjing 210023, Jiangsu, China

Received date: 2021-10-21

  Online published: 2025-03-08

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.

摘要

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|$

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

本文引用格式

齐林明, 赵伟良, 苗连英 . 边染色临界图独立数的新下界[J]. 运筹学学报, 2025 , 29(1) : 225 -231 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.019

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\}$.

参考文献

1 Vizing V G . Some unsolved problems in graph theory[J]. Uspekhi Matematicheskikh Nauk, 1968, 23 (6): 117- 134.
2 逢世友, 马国翼, 苗连英. 临界图独立数的上界[J]. 徐州师范大学学报(自然科学版), 2010, 28 (1): 15-16+27.
3 Miao L Y . On the indepence number of edge chromatic critical graphs[J]. Ars Combinatoria, 2011, 98, 471- 481.
4 Zhang L . Every planar graph with maximum degree 7 is of class 1[J]. Graphs and Combinatorics, 2000, 16, 467- 495.
5 Luo R , Miao L Y , Zhao Y . The size of edge chromatic critical graphs with maximum degree 6[J]. Graphs Theory, 2009, 60, 149- 171.
6 Sanders D , Yue Z . Planar graphs with maximum degree seven are class 1[J]. Journal of Combinatorial Theory, 2001, 83 (2): 201- 212.
7 Li S C , Li X C . Edge coloring of graphs with small maximum degree[J]. Discrete Mathematics, 2009, 309, 4843- 4852.
文章导航

/