Distance edge-colourings and matchings
| Autor: | Putra Manggala, Ross J. Kang |
|---|---|
| Jazyk: | angličtina |
| Předmět: |
Random graph
Discrete mathematics Matching (graph theory) Applied Mathematics 010102 general mathematics Strong perfect graph theorem 0102 computer and information sciences 01 natural sciences Upper and lower bounds Combinatorics Strong chromatic index Indifference graph Edge coloring Induced matchings 010201 computation theory & mathematics Chordal graph Random regular graph Graph colouring Discrete Mathematics and Combinatorics 0101 mathematics Distance edge-colouring Mathematics Random graphs |
| Zdroj: | Discrete Applied Mathematics. (16-17):2435-2439 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2012.07.001 |
| Popis: | 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ń. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|