We consider a distance generalisation of the strong chromatic index and the maximum induced matching number. We study graphs of bounded maximum degree and Erd\H{o}s–R\'{e}nyi random graphs. We work in three settings. The first is that of a distance generalisation of an Erd\H{o}s–Ne\v{s}et\v{r}il problem. The second is that of an upper bound on the size of a largest distance matching in a random graph. The third is that of an upper bound on the distance chromatic index for sparse random graphs. One of our results gives a counterexample to a conjecture of Skupie\'{n}.

Additional Metadata
Keywords Graph colouring, Strong chromatic index, Induced matchings, Distance edge-colouring, Random graphs
MSC Coloring of graphs and hypergraphs (msc 05C15), Factorization, matching, partitioning, covering and packing (msc 05C70)
THEME Logistics (theme 3)
Publisher Elsevier
Journal Discrete Applied Mathematics
Project Generalised colouring fro random graph models
Citation
Kang, R.J, & Manggala, P. (2012). Distance edge-colourings and matchings. Discrete Applied Mathematics, 160(16-17), 2435–2439.