Noon lecture

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

On 07.12.2006 at 12:20 in S5, there is the following noon lecture:

Circular Arboricity of Graphs

Jan van den Heuvel

London School of Economics

Abstract

For a real positive number a, let Ra denote the circle with circumference a. Given a graph G (with possible multiple edges, but no loops), we want to map the edges of G to Ra so that for every unit interval, the edges mapped into that interval contain no cycle (i.e., induce a forest). In particular, we like to know the minimum value of a for which such a mapping is possible.

Since for every subgraph H of G a unit interval cannot contain more than |V(H)|-1 edges from H, we easily have that we must take a at least max{|E(H)|/(|V(H)|-1)}, where the maximum is taken over all subgraphs H of G with |E(H)|>0. Daniel Goncalves conjectured that in fact equality holds for all graphs.<BR> This conjecture generalises a classical result

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

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