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