Options
Bounds for the independence number of critical graphs
Date Issued
2000
Author(s)
Brinkmann, G
Choudum, SA
Grunewald, S
Steffen, E
Abstract
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, alpha(G) less than or equal to 1/2\V(G)\. Let Delta be the maximum vertex degree in a critical graph. For each Delta, we determine c(Delta) such that alpha(G) less than or equal to c(Delta)\V\.
Volume
32