The mod k k chromatic index of random graphs

Abstract: The

chromatic index of a graph

G

is the minimum number of colors needed to color the edges of

G

in a way that the subgraph spanned by the edges of each color has all degrees congruent to

1!! p m o d k

. Recently, the authors proved that the

chromatic index of every graph is at most

198 k - 101

, improving, for large

k

, a result of Scott [Discrete Math. 175, 1-3 (1997), 289-291]. Here we study the

chromatic index of random graphs. We prove that for every integer

k g e q 2

, there is

C_{k} > 0

such that if

p g e q C_{k} n^{- 1} l o g n

and

n (1 - p) i g h t a r r o w i n f t y

as

n o i n f t y

, then the following holds: if

k

is odd, then the

chromatic index of

G (n, p)

is asymptotically almost surely equal to

k

, while if

k

is even, then the

chromatic index of

G (2 n, p)

(respectively

G (2 n + 1, p)

) is asymptotically almost surely equal to

k

(respectively

k + 1

).

Recommendations

Cites work

Cited in

(3)

This page was built for publication: The mod k $k$ chromatic index of random graphs