# Noon lecture

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

On 7.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 **R**_{a} 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 **R**_{a} 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 | 2018 | 2019 | 2020 | newer lectures)

Webmaster: kamweb.mff.cuni.cz Archive page