Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Rainbow matching
Résumé
In the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors.
Given an edge-colored graph G = (V,E), a rainbow matching M in G is a set of pairwise non-adjacent edges, that is, no two edges share a common vertex, such that all the edges in the set have distinct colors.
A maximum rainbow matching is a rainbow matching that contains the largest possible number of edges.
Rainbow matchings are of particular interest given their connection to transversals of Latin squares.
Denote by K_n,n the complete bipartite graph on n + n vertices. Every proper n-edge coloring of K_n,n corresponds to a Latin square of order n. A rainbow matching then corresponds to a transversal of the Latin square, meaning a selection of n positions, one in each row and each column, containing distinct entries.
This connection between transversals of Latin squares and rainbow matchings in K_n,n has inspired additional interest in the study of rainbow matchings in triangle-free graphs.
An edge-coloring is called proper if each edge has a single color, and each two edges of the same color have no vertex in common.
A proper edge-coloring does not guarantee the existence of a perfect rainbow matching. For example, consider the graph K_2,2: the complete bipartite graph on 2+2 vertices. Suppose the edges (x_1,y_1) and (x_2,y_2) are colored green, and the edges (x_1,y_2) and (x_2,y_1) are colored blue. This is a proper coloring, but there are only two perfect matchings, and each of them is colored by a single color. This invokes the question: when does a large rainbow matching is guaranteed to exist?
Much of the research on this question was published using the terminology of Latin transversals in Latin squares. Translated into the rainbow matching terminology:
In 1967, H. J. Ryser conjectured that, when n is odd, every proper edge-coloring of K_n,n has a rainbow matching of size n.
In 1975, S. K. Stein and Brualdi conjectured that, when n is even, every proper edge-coloring of K_n,n has a rainbow matching of size n – 1.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.