Cubic graph with large girth

Series
Graph Theory Seminar
Time
Thursday, June 11, 2009 - 11:05am for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Daniel Kral – ITI, Charles University, Prague
Organizer
Robin Thomas

We study several parameters of cubic graphs with large girth. In particular, we prove that every n-vertex cubic graph with sufficiently large girth satisfies the following:

  • has a dominating set of size at most 0.29987n (which improves the previous bound of 0.32122n of Rautenbach and Reed)
  • has fractional chromatic number at most 2.37547 (which improves the previous bound of 2.66881 of Hatami and Zhu)
  • has independent set of size at least 0.42097n (which improves the previous bound of 0.41391n of Shearer), and
  • has fractional total chromatic number arbitrarily close to 4 (which answers in the affirmative a conjecture of Reed). More strongly, there exists g such that the fractional total chromatic number of every bridgeless graph with girth at least g is equal to 4.
The presented bounds are based on a simple probabilistic argument.

The presentation is based on results obtained jointly with Tomas Kaiser, Andrew King, Petr Skoda and Jan Volec.