The emergence of collective properties in systems composed of many interacting units has traditionally been studied in terms of some property or state characterizing each of these units. However, there is a number of situations in which the variable of interest is a characteristic of the interaction link instead of a feature of the interacting units. The study of co-evolving dynamics and network topologies has also received much attention recently, particularly in the context of social systems and always from a node states perspective. We present here a co-evolution model that couples the dynamics of link states with the evolution of the network's topology. Each link can be in one of two equivalent states and they are updated according to the majority rule or zero-temperature Glauber dynamics. Additionally, we define a rewiring mechanism inspired by the case of competing languages. Depending on the relative speed of the majority rule and the rewiring processes, the system evolves towards different absorbing configurations and we find a fragmentation transition. By means of a scaling analysis and a mean-field approach we characterize the fragmentation transition and describe the ordering of the system and its convergence time for large rewiring values.