Average degrees of edge-chromatic critical graphs (Q1999729)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Average degrees of edge-chromatic critical graphs |
scientific article |
Statements
Average degrees of edge-chromatic critical graphs (English)
0 references
27 June 2019
0 references
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.
0 references
edge-\(k\)-coloring
0 references
edge-critical graphs
0 references
Vizing's adjacency lemma
0 references