Chromatic index, treewidth and maximum degree (Q5916063)

From MaRDI portal
scientific article; zbMATH DE number 6873182
Language Label Description Also known as
English
Chromatic index, treewidth and maximum degree
scientific article; zbMATH DE number 6873182

    Statements

    Chromatic index, treewidth and maximum degree (English)
    0 references
    0 references
    0 references
    0 references
    25 May 2018
    0 references
    Summary: We conjecture that any graph \(G\) with treewidth \(k\) and maximum degree \(\Delta(G)\geq k + \sqrt{k}\) satisfies \(\chi'(G)=\Delta(G)\). In support of the conjecture we prove its fractional version. We also show that any graph \(G\) with treewidth \(k\geq 4\) and maximum degree \(2k-1\) satisfies \(\chi'(G)=\Delta(G)\), extending an old result of Vizing.
    0 references
    graph theory
    0 references
    edge colouring
    0 references
    fractional edge colouring
    0 references
    tree width
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references