A comparison of two edge-coloring formulations

DOI10.1016/0167-6377(93)90043-GzbMath0783.05049MaRDI QIDQ688209

Jon Lee, Janny M. Y. Leung

Publication date: 28 November 1993

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

integer programmingNP-completechromatic indexmaximum degreeVizing's theorem

Mathematics Subject Classification ID

Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items

An exact algorithm for the edge coloring by total labeling problem, Total coloring and total matching: polyhedra and facets, Separating type-I odd-cycle inequalities for a binary-encoded edge-coloring formulation, How important are branching decisions: fooling MIP solvers, Properties of some ILP formulations of a class of partitioning problems

Uses Software

• GAMS

Cites Work

• Unnamed Item
• Unnamed Item
• A new method of proving theorems on chromatic index
• Matching theory
• The ellipsoid method and its consequences in combinatorial optimization
• A polyhedral approach to edge coloring
• The NP-Completeness of Edge-Coloring
• Odd Minimum Cut-Sets and b-Matchings
• Maximum matching and a polyhedron with 0,1-vertices