A new upper bound for the independence number of edge chromatic critical graphs |
| |
| Authors: | Rong Luo Yue Zhao |
| |
| Affiliation: | 1. Department of Mathematical Sciences Middle Tennessee State University Murfreesboro, TN 37132;2. Department of Mathematics University of Central Florida, Orlando, FL 32816‐1364 |
| |
| Abstract: | In 1968, Vizing conjectured that if G is a Δ‐critical graph with n vertices, then α(G)≤n/2, where α(G) is the independence number of G. In this paper, we apply Vizing and Vizing‐like adjacency lemmas to this problem and prove that α(G)<(((5Δ?6)n)/(8Δ?6))<5n/8 if Δ≥6. © 2010 Wiley Periodicals, Inc. J Graph Theory 68: 202‐212, 2011 |
| |
| Keywords: | edge coloring independence number critical graphs |
|
|
