Color neighborhood union conditions for long heterochromatic paths in edge-colored graphs

Abstract: Let

G

be an edge-colored graph. A heterochromatic (rainbow, or multicolored) path of

G

is such a path in which no two edges have the same color. Let

d^{c} (v)

denote the color degree and

C N (v)

denote the color neighborhood of a vertex

v

of

G

. In a previous paper, we showed that if

d^{c} (v) g e q k

(color degree condition) for every vertex

v

of

G

, then

G

has a heterochromatic path of length at least

l c e i l f r a c k + 1 2 c e i l

, and if

| C N (u) c u p C N (v) | g e q s

(color neighborhood union condition) for every pair of vertices

u

and

v

of

G

, then

G

has a heterochromatic path of length at least

l c e i l f r a c s 3 c e i l + 1

. Later, in another paper we first showed that if

k l e q 7

,

G

has a heterochromatic path of length at least

k - 1

, and then, based on this we use induction on

k

and showed that if

k g e q 8

, then

G

has a heterochromatic path of length at least

l c e i l f r a c 3 k 5 c e i l + 1

. In the present paper, by using a simpler approach we further improve the result by showing that if

k g e q 8

,

G

has a heterochromatic path of length at least

l c e i l f r a c 2 k 3 c e i l + 1

, which confirms a conjecture by Saito. We also improve a previous result by showing that under the color neighborhood union condition,

G

has a heterochromatic path of length at least

l f l o o r f r a c 2 s + 4 5 f l o o r

.

Full work available at URL: https://arxiv.org/abs/math/0512144

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

Cited In (8)

This page was built for publication: Color neighborhood union conditions for long heterochromatic paths in edge-colored graphs