DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Andrew Baxter, Rutgers University, baxter{at} math [dot] rutgers [dot] edu

Lara Pudwell, Rutgers University, lpudwell {at} math [dot] rutgers [dot] edu

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: Critical Triangle-free Graphs with Lots of Edges

Speaker: Wes Pegden, Rutgers University

Date: Thursday, February 7, 2008 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

How close are the triangle-free graphs to the bipartite graphs? The different ways of asking this question give different answers. For example: on the one hand, triangle-free graphs can have arbitrarily large chromatic number; on the other, natural constructions to demonstrate this fact are typically very sparse. One type of question with this theme is the recently solved question of Erdos and Simonovits, which asks about triangle-free graphs with large chromatic number and large minimum degree.

We consider a different question with the same motivation: are there k-chromatic-critical triangle-free graphs with lots of edges for arbitrarily large k? We'll talk about a construction that shows that the answer is yes. We'll also show how one can nonconstructively extend the result to graphs without pentagons as well. Results about the density of general critical graphs typically leave wide gaps between what we know as upper and lower bounds; the case of triangle-free graphs seems unusual in this context, since our construction actually shows the exact maximum asymptotic density.