## Abstract

For a graph G, a strong edge coloring of G is an edge coloring in which every color class is an induced matching. The strong chromatic index of G,χ_{s}(G), is the smallest number of colors in a strong edge coloring of G. Palka (Austral. J. Combin. 18 (1998) 219-226), proved that if p=p(n)=Θ(n^{-1}), then with high probability, χ _{s}(G(n,p))=O(Δ(G(n,p))). Recently Vu (Combin. Probab. Comput. 11 (2002) 103-111), proved that if n^{-1}(lnn) ^{1+δ}≤p=p(n)≤n^{-ε} for any 0<ε,δ<1, then with high probability, χ _{s}(G(n,p))=O((pn)^{2}/ln(pn)). In this note, we prove that if p=p(n)>n^{-ε} for all ε>0, then with b=(1-p) ^{-1}, with high probability, (1-o(1))(pn2/log _{b}n)≤χ_{s}(G(n,p))≤(2+o(1))(pn2/log_{b}n).

Original language | English (US) |
---|---|

Pages (from-to) | 129-136 |

Number of pages | 8 |

Journal | Discrete Mathematics |

Volume | 281 |

Issue number | 1-3 |

DOIs | |

State | Published - Apr 28 2004 |

## Keywords

- Random graphs
- Strong chromatic index

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics