# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | future lectures)

On 26.10.2010 at 12:20 in S10, there is the following noon lecture:

# Coloring Graphs via VC_dimension

## Stephan Thomasse

## Abstract

We provide an upper bound on the chromatic number of graphs only depending of its fractional domination and a new complexity invariant for graphs called "paired VC dimension".

As a corollary, we directly obtain that for instance a graph G without Petersen subgraph and minimum degree n/10000 has bounded chromatic number.

We also characterize the graphs H such that H-free graphs with linear degree have bounded chromatic number.

This is joint work with T. Luczak.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | future lectures)

Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010