Rainbow matching

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.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (36)

Related people (5)

Related units (6)

Related concepts (2)

Related courses (4)

Related lectures (17)

Matching in hypergraphs

In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph. Recall that a hypergraph H is a pair (V, E), where V is a set of vertices and E is a set of subsets of V called hyperedges. Each hyperedge may contain one or more vertices. A matching in H is a subset M of E, such that every two hyperedges e_1 and e_2 in M have an empty intersection (have no vertex in common).

Edge coloring

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors.

CS-448: Sublinear algorithms for big data analysis

In this course we will define rigorous mathematical models for computing on large datasets, cover main algorithmic techniques that have been developed for sublinear (e.g. faster than linear time) data

CS-450: Algorithms II

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a reper

CS-250: Algorithms I

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

Equivariant Neural Architectures for Representing and Generating Graphs

Clément Arthur Yvon Vignac

Graph machine learning offers a powerful framework with natural applications in scientific fields such as chemistry, biology and material sciences. By representing data as a graph, we encode the prior knowledge that the data is composed of a set of entitie ...

EPFL2023

SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators

Nathanaël Perraudin, Andreas Loukas, Karolis Martinkus

We approach the graph generation problem from a spectral perspective by first generating the dominant parts of the graph Laplacian spectrum and then building a graph matching these eigenvalues and eigenvectors. Spectral conditioning allows for direct model ...

JMLR-JOURNAL MACHINE LEARNING RESEARCH2022

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

Akash Kumar

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...

IEEE COMPUTER SOC2022

Explores linear programming duality, covering constraints, variables, solutions, and the relationship between primal and dual LP.

Covers linear programming, weighted bipartite matching, and vertex cover problems in optimization.

Explores the Ford-Fulkerson method, max-flow, applications of max-flow, and the disjoint-set data structure.