Restricted subgraphs of edge-colored graphs and applications

Abstract

A properly edge-colored graph is a graph with a coloring of its edges such that no vertex is incident to two or more edges of the same color. A subgraph is called rainbow if all its edges have different colors. The problem of finding rainbow subgraphs or other restricted structures in edge-colored graphs has a long history, dating back to Euler’s work on Latin squares. It has also proven to be a powerful method for studying several well-known questions in other areas.

In this survey, we will provide a brief introduction to this topic, discuss several results in this area and demonstrate their applications to problems in graph decomposition, additive combinatorics, theoretical computer science and coding theory.