An Edge-Colored Version of Dirac's Theorem

Abstract: Let

G

be an edge-coloured graph. The minimum colour degree

d e l t a^{c} (G)

of

G

is the largest integer

k

such that, for every vertex

v

, there are at least

k

distinct colours on edges incident to

v

. We say that

G

is properly coloured if no two adjacent edges have the same colour. In this paper, we show that every edge-coloured graph

G

with

d e l t a^{c} (G) g e 2 | G | / 3

contains a properly coloured

2

-factor. Furthermore, we show that for any

v a r e p s i l o n > 0

there exists an integer

n_{0}

such that every edge-coloured graph

G

with

| G | = n g e n_{0}

and

d e l t a^{c} (G) g e (2 / 3 + v a r e p s i l o n) n

contains a properly coloured cycle of length

e l l

for every

3 l e e l l l e n

. This result is best possible in the sense that the statement is false for

d e l t a^{c} (G) < 2 n / 3

.

Recommendations

Cited In (25)

This page was built for publication: An Edge-Colored Version of Dirac's Theorem