MATH Seminar

Title: Bounding the Chromatic Number and Average Degree of Graphs
Job Talk: Combinatorics
Speaker: Rose McCarty, Instructor and NSF Postdoctoral of Princeton University
Contact: Liana Yepremyan, liana.yepremyan@emory.edu
Date: 2023-01-12 at 10:00AM
Venue: MSC W201
Download Flyer
Abstract: When can we partition the vertex set of a graph into a few parts so that, within each part, there are no adjacent vertices? One obvious obstruction is the existence of many pairwise adjacent vertices. A class of graphs is called $\chi$-bounded if this is the only obstruction. We introduce this topic by considering classes of graphs with geometric representations. Then we move on to the general case. While it was recently shown that $\chi$-bounding functions can be arbitrarily bad, we prove that "average degree bounding functions" are actually well-behaved. This proof suggests a new approach to the 1983 conjecture of Thomassen about average degree and girth.