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
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