Some results on the rainbow vertex-disconnection colorings of graphs

Abstract: Let

G

be a nontrivial connected and vertex-colored graph. A vertex subset

X

is called rainbow if any two vertices in

X

have distinct colors. The graph

G

is called emph{rainbow vertex-disconnected} if for any two vertices

x

and

y

of

G

, there exists a vertex subset

S

such that when

x

and

y

are nonadjacent,

S

is rainbow and

x

and

y

belong to different components of

G - S

; whereas when

x

and

y

are adjacent,

S + x

or

S + y

is rainbow and

x

and

y

belong to different components of

(G - x y) - S

. For a connected graph

G

, the emph{rainbow vertex-disconnection number} of

G

,

r v d (G)

, is the minimum number of colors that are needed to make

G

rainbow vertex-disconnected. In this paper, we prove for any

K_{4}

-minor free graph,

r v d (G) l e q D e l t a (G)

and the bound is sharp. We show it is

N P

-complete to determine the rainbow vertex-disconnection number for bipartite graphs and split graphs. Moreover, we show for every

e p s i l o n > 0

, it is impossible to efficiently approximate the rainbow vertex-disconnection number of any bipartite graph and split graph within a factor of

n^{f r a c 13 - e p s i l o n}

unless

Z P P = N P

.

Recommendations

This page was built for publication: Some results on the rainbow vertex-disconnection colorings of graphs