Cubic graph with large girth

Graph Theory Seminar
Thursday, June 11, 2009 - 11:05
1 hour (actually 50 minutes)
Skiles 255
ITI, Charles University, Prague

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.