Thumbnail - Request a copy

Kőnig’s edge-colouring theorem for all graphs

Nguyen, Viet Hung; Cornaz, Denis (2013), Kőnig’s edge-colouring theorem for all graphs, Operations Research Letters, 41, 6, p. 592-596. http://dx.doi.org/10.1016/j.orl.2013.08.005

Type
Article accepté pour publication ou publié
Date
2013-11-02
Journal name
Operations Research Letters
Volume
41
Number
6
Publisher
Elsevier
Pages
592-596
Publication identifier
Metadata
Show full item record
Author(s)
Nguyen, Viet Hung

Cornaz, Denis
Abstract (EN)
We show that the maximum degree of a graph G is equal to the minimum number of ocm sets covering G, where an ocm set is the vertex-disjoint union of elementary odd cycles and one matching, and a collection of ocm sets covers G if every edge is in the matching of an ocm set or in some odd cycle of at least two ocm sets.
Subjects / Keywords
TDI system; Substar polytope; Kőnig’s edge-colouring theorem