Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419813 | Discrete Applied Mathematics | 2012 | 5 Pages |
Abstract
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ős–Rényi random graphs. We work in three settings. The first is that of a distance generalisation of an Erdős–Nešetř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ń.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ross J. Kang, Putra Manggala,