A note on the vertex arboricity of signed graphs

Abstract: A signed tree-coloring of a signed graph

(G, s i g m a)

is a vertex coloring

c

so that

G^{c} (i, p m)

is a forest for every

i i n c (u)

and

u i n V (G)

, where

G^{c} (i, p m)

is the subgraph of

(G, s i g m a)

whose vertex set is the set of vertices colored by

i

or

- i

and edge set is the set of positive edges with two end-vertices colored both by

i

or both by

- i

, along with the set of negative edges with one end-vertex colored by

i

and the other colored by

- i

. If

c

is a function from

V (G)

to

M_{n}

, where

M_{n}

is

p m 1, p m 2, l d o t s, p m k

if

n = 2 k

, and

0, p m 1, p m 2, l d o t s, p m k

if

n = 2 k + 1

, then

c

a signed tree-

n

-coloring of

(G, s i g m a)

. The minimum integer

n

such that

(G, s i g m a)

admits a signed tree-

n

-coloring is the signed vertex arboricity of

(G, s i g m a)

, denoted by

v a (G, s i g m a)

. In this paper, we first show that two switching equivalent signed graphs have the same signed vertex arboricity, and then prove that

v a (G, s i g m a) l e q 3

for every balanced signed triangulation and for every edge-maximal

K_{5}

-minor-free graph with balanced signature. This generalizes the well-known result that the vertex arboricity of every planar graph is at most 3.

Recommendations

Cited in

(1)

This page was built for publication: A note on the vertex arboricity of signed graphs