中文

Operations Research Transactions >

2025 , Vol. 29 >Issue 1: 225 - 231

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2025.01.019

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.
Fold

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

Cite this article

Linming QI, Weiliang ZHAO, Lianying MIAO . The lower limit of the independence number in edge chromatic critical graphs[J]. Operations Research Transactions, 2025 , 29(1) : 225 -231 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.019

References

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.
Options
Outlines

/

〈 〉