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.
%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
}