Average degrees of edge-chromatic critical graphs (Q1999729): Difference between revisions

A graph \(G\) with maximum degree \(\Delta\) is \(\Delta\)-critical if \(\chi^\prime(G) = \Delta+1\) and any proper subgraph \(H\) of \(G\) satisfies \(\chi^\prime(H) \le \Delta\). There is the longstanding Vizing average degree conjecture stating that any \(\Delta\)-critical graph \(G\) with average degree \(\overline{d}\) and order \(n\) satisfies \(\overline{d} \ge \Delta - 1 + \frac{3}{n}\). There have been quite a few former results towards this conjecture. The current research deploys well-designed discharging rules to prove that for any \(\delta\)-critical graph, depending on whether \(\Delta \le 75\) or \(\Delta \ge 76\), \(\overline{d}\) can be upper bounded by a linear function of \(\Delta\), which yields the best known results in this direction so far.