Bounding the strong chromatic index of dense random graphs
type: Item
instance of: scholarly article
title: Bounding the strong chromatic index of dense random graphs
zbMATH Open document ID: 1044.05062
author: Andrzej Czygrinow
author: B. Nagle
published in: Discrete Mathematics
publication date: 2004-08-06T00:00:00Z
review text: For a finite simple graph \(G\), a strong edge colouring of \(G\) is an edge colouring in which every colour class is an induced matching. (Since each class is a matching, the colouring is proper.) The strong chromatic index of \(G\), \(\chi_{s}(G)\), is the smallest number of colours in a strong edge colouring of \(G\). The paper under review studies the strong chromatic index of random graphs \(G(n,p(n))\) where each edge arises with probability \(p(n)\) independently of all other edges. \textit{Z. Palka} [Australas. J. Comb. 18, 219-226 (1998; Zbl 0923.05042)] showed that if \(p(n)=\Theta(n^{-1})\), then \[ \lim_{n\rightarrow\infty}P\{\chi_{s}(G(n,p(n)))=O(\Delta(G(n,p(n))))\}=1 \] where, as usual, \(\Delta=\Delta(G)\) is the maximum degree of the graph. \textit{V. H. Vu} [Comb. Probab. Comput. 11, 103--111 (2002; Zbl 0991.05041)] used Rödl-nibble type arguments to show that if \(\log(n)^{1+\delta}/n\leq p(n)\leq n^{-\varepsilon}\) for any \(\varepsilon>0\) and \(\delta<1\), then \[ \lim_{n\rightarrow\infty}P\{\chi_{s}(G(n,p(n)))=O(\Delta^{2}/\log(\Delta))\}=1. \] These two papers between them cover most cases where \(p=o(1)\). (When \(p(n)=o(1/n)\) the random graph is usually a forest and the strong chromatic index of a tree is well understood: in particular, it is less than \(2\Delta\).) The aim of the paper under review is to study the case where \(p(n)>n^{-\varepsilon}\) for all \(\varepsilon>0\). The main result is that \[ \lim_{n\rightarrow\infty}P\{\frac{(1-o(1))p{n\choose 2}}{\log_{1/(1-p)}(n)}\leq \chi_{s}(G(n,p(n)))\leq \frac{(2+o(1))p{n\choose 2}}{\log_{1/(1-p)}(n)}\}=1. \] The lower bound is easy: a typical \(G(n,p)\) has about \(p{n\choose 2}\) edges and it is easy to see, using the first moment method, that the largest induced matching in \(G(n,p)\) has about \(\log_{1/(1-p)}(n)\) edges. More interesting part is the upper bound, derived from the result of \textit{B. Bollobás} [Combinatorica 8, 49--56 (1988; Zbl 0666.05033)] to the effect that the (o…
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 2083663
zbMATH Keywords: strong chromatic index
zbMATH Keywords: random graphs
reviewed by: David B. Penman
MaRDI profile type: Publication
full work available at URL: j.disc.2003.09.009
OpenAlex ID: W1967598767
cites work: The strong chromatic index of a cubic graph is at most 10
cites work: The chromatic number of random graphs
cites work: Strong edge colorings of uniform graphs
cites work: Q4519896
cites work: Q4878666
cites work: A bound on the strong chromatic index of a graph
cites work: Q4222086
cites work: On a packing and covering problem
cites work: Q4200109
cites work: A General Upper Bound on the List Chromatic Number of Locally Sparse Graphs
DOI: 10.1016/J.DISC.2003.09.009
description: scientific article; zbMATH DE number 2083663