The independence number of an edge‐chromatic critical graph |
| |
Authors: | Douglas R Woodall |
| |
Institution: | School of Mathematical Sciences, University of Nottingham, Nottingham NG7 2RD, United Kingdom |
| |
Abstract: | A graph G with maximum degree Δ and edge chromatic number χ′(G)>Δ is edge‐Δ‐critical if χ′(G?e)=Δ for every edge e of G. It is proved here that the vertex independence number of an edge‐Δ‐critical graph of order n is less than . For large Δ, this improves on the best bound previously known, which was roughly ; the bound conjectured by Vizing, which would be best possible, is . © 2010 Wiley Periodicals, Inc. J Graph Theory 66:98‐103, 2011 |
| |
Keywords: | adjacency lemma chromatic index edge coloring edge‐critical graph |
|
|