Colorful complete bipartite subgraphs in generalized Kneser graphs
Time: 11:00 -- Location: Salle Philippe Flajolet du LIX
Any proper coloring of a Kneser graph with a minimum number of colors contains an almost-complete bipartite subgraph with all colors on each side. (An almost-complete bipartite graph is a complete bipartite graph minus a perfect matching.) This is a theorem due to Chen (2012), which solved a conjecture about the circular chromatic number of Kneser graphs. We prove that such a "colorful" subgraph still exists for the generalized Kneser graphs (obtained from any hypergraph), and for their categorical products, when they match a certain topological lower bound for the chromatic number (Dol’nikov’s bound). This result has some consequences for the circular chromatic number and Hedetniemi’s conjecture.
Joint work with Meysam Alishahi and Hossein Hajiabolhassan.