A comparison of two edge-coloring formulations (Q688209)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A comparison of two edge-coloring formulations |
scientific article; zbMATH DE number 440371
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A comparison of two edge-coloring formulations |
scientific article; zbMATH DE number 440371 |
Statements
A comparison of two edge-coloring formulations (English)
0 references
28 November 1993
0 references
Vizing's theorem asserts that the chromatic index \(\chi(G)\) is either \(\Delta(G)\) or \(\Delta(G)+1\), where \(\Delta(G)\) is the maximum degree of a graph \(G\). However, determining which of these two alternatives holds is NP-complete. This paper provides a polyhedral formulation for determining \(\chi(G)\), by which it is allowed analytically and computationally to compare to the set-partitioning formulation. Some valid inequalities for this formulation are established.
0 references
integer programming
0 references
Vizing's theorem
0 references
chromatic index
0 references
maximum degree
0 references
NP-complete
0 references
