  Let G = (V, E, L) be an edge-labeled graph such that V is the set of
vertices, E is the set of edges, L is the set of labels (colors) and each edge
e \in E has a label l(e) associated; The goal of the minimum labeling global
cut problem (MLGCP) is to find a subset L \subseteq L of labels such that G =
(V, E , L\L ) is not connected and |L| is minimized. This work proposes three
new mathematical formulations for the MLGCP as well as branch-and-cut
algorithms to solve them. The computational experiments showed that the
proposed methods are able to solve small to average sized instances in a
reasonable amount of time.
