%0 Generic %1 Nesetril2011 %A Nesetril, Jaroslav %A Mendez, Patrice Ossona De %A Zhu, Xuding %D 2011 %K colouring colours constrained cycles edges %T Colouring Edges with many Colours in Cycles %U http://arxiv.org/abs/1108.1616 %X 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.

@misc{Nesetril2011, 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. }, added-at = {2011-08-10T20:09:47.000+0200}, author = {Nesetril, Jaroslav and Mendez, Patrice Ossona De and Zhu, Xuding}, biburl = {https://www.bibsonomy.org/bibtex/21fc87f66cc62acd55b5b9ed3e7bd44b9/pom}, description = {Colouring Edges with many Colours in Cycles}, interhash = {85143411e3c90377ae77ab9622ddddc5}, intrahash = {1fc87f66cc62acd55b5b9ed3e7bd44b9}, keywords = {colouring colours constrained cycles edges}, note = {cite arxiv:1108.1616}, timestamp = {2011-08-10T20:09:47.000+0200}, title = {Colouring Edges with many Colours in Cycles}, url = {http://arxiv.org/abs/1108.1616}, year = 2011 }