MATH Seminar

Title: Bounded colorings of graphs and hypergraphs
Seminar: Combinatorics
Speaker: Jan Volec of McGill University
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2017-02-27 at 4:00PM
Venue: MSC W303
Download Flyer
Abstract: 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 was 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 have bounded maximum degree or 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 is 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 is 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. The talk is based on a joint work with Nina Kamcev and Benny Sudakov.