Equitable vertex arboricity of graphs

Abstract: An equitable

(t, k, d)

-tree-coloring of a graph

G

is a coloring to vertices of

G

such that the sizes of any two color classes differ by at most one and the subgraph induced by each color class is a forest of maximum degree at most

k

and diameter at most

d

. The minimum

t

such that

G

has an equitable

(t^{'}, k, d)

-tree-coloring for every

t^{'} g e q t

is called the strong equitable

(k, d)

-vertex-arboricity and denoted by

v a_{k, d}^{e q u i v} (G)

. In this paper, we give sharp upper bounds for

v a_{1, 1}^{e q u i v} (K_{n, n})

and

v a_{k, i n f t y}^{e q u i v} (K_{n, n})

by showing that

v a_{1, 1}^{e q u i v} (K_{n, n}) = O (n)

and

v a_{k, i n f t y}^{e q u i v} (K_{n, n}) = O (n^{1 / 2})

for every

k g e q 2

. It is also proved that

v a_{i n f t y, i n f t y}^{e q u i v} (G) l e q 3

for every planar graph

G

with girth at least 5 and

v a_{i n f t y, i n f t y}^{e q u i v} (G) l e q 2

for every planar graph

G

with girth at least 6 and for every outerplanar graph. We conjecture that

v a_{i n f t y, i n f t y}^{e q u i v} (G) = O (1)

for every planar graph and

v a_{i n f t y, i n f t y}^{e q u i v} (G) l e q l c e i l f r a c D e l t a (G) + 1 2 c e i l

for every graph

G

.

Recommendations

Cites work

Cited in

(23)

This page was built for publication: Equitable vertex arboricity of graphs