Abstract
The arboricity of a graph G is the minimum number of colours needed to colour
the edges of G so that every cycle gets at least two colours. Given a positive
integer p, we define the generalized p-arboricity Arb_p(G) of a graph G as the
minimum number of colours needed to colour the edges of a multigraph G in such
a way that every cycle C gets at least min(|C|; p + 1) colours. In the
particular case where G has girth at least p + 1, Arb_p(G) is the minimum size
of a partition of the edge set of G such that the union of any p parts induce a
forest. If we require further that the edge colouring be proper, i.e., adjacent
edges receive distinct colours, then the minimum number of colours needed is
the generalized p-acyclic edge chromatic number of G. In this paper, we relate
the generalized p-acyclic edge chromatic numbers and the generalized
p-arboricities of a graph G to the density of the multigraphs having a shallow
subdivision as a subgraph of G.
Users
Please
log in to take part in the discussion (add own reviews or comments).