- Graph Theory Seminar
- Thursday, June 11, 2009 - 11:05am for 1 hour (actually 50 minutes)
- Skiles 255
- Daniel Kral – ITI, Charles University, Prague
- 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 presentation is based on results obtained jointly with Tomas Kaiser, Andrew King, Petr Skoda and Jan Volec.