Abstract
Let (Formula presented.) be a simple graph with maximum degree (Formula presented.) and chromatic index (Formula presented.). A classical result of Vizing shows that either (Formula presented.) or (Formula presented.). A simple graph (Formula presented.) is called edge- (Formula presented.) -critical if (Formula presented.) is connected, (Formula presented.) and (Formula presented.) for every (Formula presented.). Let (Formula presented.) be an (Formula presented.) -vertex edge- (Formula presented.) -critical graph. Vizing conjectured that (Formula presented.), the independence number of (Formula presented.), is at most (Formula presented.). The current best result on this conjecture, shown by Woodall, is (Formula presented.). We show that for any given (Formula presented.), there exist positive constants (Formula presented.) and (Formula presented.) such that if (Formula presented.) is an (Formula presented.) -vertex edge- (Formula presented.) -critical graph with minimum degree at least (Formula presented.) and maximum degree at least (Formula presented.), then (Formula presented.). In particular, we show that if (Formula presented.) is an (Formula presented.) -vertex edge- (Formula presented.) -critical graph with minimum degree at least (Formula presented.) and (Formula presented.), then (Formula presented.).
| Original language | English (US) |
|---|---|
| Pages (from-to) | 288-310 |
| Number of pages | 23 |
| Journal | Journal of Graph Theory |
| Volume | 101 |
| Issue number | 2 |
| DOIs | |
| State | Published - Oct 2022 |
| Externally published | Yes |
Keywords
- Vizing's independence number conjecture
- chromatic index
- edge-chromatic critical graph
ASJC Scopus subject areas
- Geometry and Topology
- Discrete Mathematics and Combinatorics