Combinatorics Seminar

When: Sunday, January 1, 10am Where: Schreiber 309 Speaker: Benny Sudakov, University of California at Los Angeles Title: Chromatic number, clique subdivisions, and the conjectures of Hajos and Erdos-Fajtlowicz

Abstract:

For a graph G, let \chi(G) denote its chromatic number and \sigma(G) denote the order of the largest clique subdivision in G. Let H(n) be the maximum of \chi(G)/\sigma(G) over all n-vertex graphs G. A famous conjecture of Hajos from 1961 states that \sigma(G)>= \chi(G) for every graph G. That is, H(n)<=1 for all positive integers n. This conjecture was disproved by Catlin in 1979. Erdos and Fajtlowicz further showed by considering a random graph that H(n)>= cn^{1/2}/\log n for some absolute constant c>0. In 1981 they conjectured that this bound is tight up to a constant factor, i.e., \chi(G)/\sigma(G)<= O(n^{1/2}/\log n) for all n-vertex graphs G. In this talk we prove this conjecture.

Joint work with J. Fox and C. Lee.