Independence number of edge‐chromatic critical graphs
Yan Cao, Guantao Chen, Guangming Jing, Songling Shan · Journal of Graph Theory · 2022
Abstract Let be a simple graph with maximum degree and chromatic index . A classical result of Vizing shows that either or . A simple graph is called edge‐‐critical if is connected, and for every . Let be an ‐vertex edge‐‐critical graph. Vizing conjectured that , the independence number of , is at most . The current best result on this conjecture, shown by Woodall, is . We show that for any given , there exist positive constants and such that if is an ‐vertex edge‐‐critical graph with minimum degree at least and maximum degree at least , then . In particular, we show that if is an ‐vertex edge‐‐critical graph with minimum degree at least and , then