Back to Search
Start Over
The Strong Chromatic Index of Random Graphs.
- Source :
-
SIAM Journal on Discrete Mathematics . 2005, Vol. 19 Issue 3, p719. 9p. - Publication Year :
- 2005
-
Abstract
- The strong chromatic index of a graph $G$, denoted by $\chi_s(G)$, is the minimum number of colors needed to color its edges so that each color class is an induced matching. In this paper we analyze the asymptotic behavior of this parameter in a random graph $G(n,p)$, for two regions of the edge probability $p=p(n)$. For the dense case, where $p$ is a constant, $0 < p < 1$, we prove that with high probability $\chi_s(G)\le (1+o(1))\frac{3}{4}\frac{n^2p}{\log_bn}$, where $b=1/(1-p)$. This improves upon a result of Czygrinow and Nagle [{\it Discrete Math.}, 281 (2004), pp. 129--136]. For the sparse case, where $np< \frac{1}{100}\sqrt{\log n/\log\log n}$, we show that with high probability $\chi_s(G)=\Delta_1(G)$, where $\Delta_1(G)=\max\{d(u)+d(v)-1:\ (u,v)\in E(G)\}$. This improves a result of Palka [{\it Australas. J. Combin.}, 18 (1998), pp. 219--226]. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 19
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 19255684
- Full Text :
- https://doi.org/10.1137/S0895480104445757