Mathematics – Combinatorics
Scientific paper
2011-08-08
Mathematics
Combinatorics
Scientific paper
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.
de Mendez Patrice Ossona
Nesetril Jaroslav
Zhu Xuding
No associations
LandOfFree
Colouring Edges with many Colours in Cycles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Colouring Edges with many Colours in Cycles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Colouring Edges with many Colours in Cycles will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-189670