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
    0 references
    0 references
    0 references
    0 references
    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
    0 references
    edge-\(k\)-coloring
    0 references
    edge-critical graphs
    0 references
    Vizing's adjacency lemma
    0 references

    Identifiers