Department of
Applied
Mathematics

Bounded colorings of graphs and hypergraphs

Jan Volec

Abstract

(joint work with Nina Kamcev and Benny Sudakov)

A conjecture of Bollobas and Erdos from 1976 states that any coloring of edges of an n-vertex complete graph such that at each vertex no color appears more than (n/2)-times contains a properly-colored Hamilton cycle. This problem served as motivation for the following more general question: Let c be a coloring of E(K_n) where at each vertex, no color appear more than k-times. What properly colored subgraphs does c necessarily contain?

In this talk, we will be interested in spanning subgraphs of K_n that has bounded maximum degree or bounded the total number of cherries, i.e., the paths on three vertices. We will also mention similar questions for hypergraphs, as well as analogous problems concerned with rainbow subgraphs in edge colorings of K_n where the total number of appearances for each color are bounded.

One of our main results confirms the following conjecture of Shearer from 1979: If G is an n-vertex graph with O(n) cherries and c a coloring of E(K_n) such that at each vertex every color appears only constantly many times, then c contains a properly colored copy of G.