Bounds for the Independence Number of Critical Graphs
Gunnar Brinkmann, S.A. Choudum, Stefan Grünewald, Eckhard Steffen · Bulletin of the London Mathematical Society · 2000
In 1968 Vizing conjectured that any independent vertex set of an edge-chromatic critical graph G contains at most half of the vertices of G, that is, α(G⩽½|(G)|). Let Δ be the maximum vertex degree in a critical graph. For each Δ, we determine c(Δ) such that α(G)⩽c(Δ)|V)|. 1991 Mathematics Subject Classification 05C15, 05C70.