Szczegóły publikacji
Opis bibliograficzny
On decomposing graphs of large minimum degree into locally irregular subgraphs / Jakub PRZYBYŁO // The Electronic Journal of Combinatorics [Dokument elektroniczny]. — Czasopismo elektroniczne ; ISSN 1077-8926. — 2016 — vol. 23 iss. 2, s. 1–13, art. no. P2.31. — Wymagania systemowe: Adobe Reader. — Bibliogr. s. 13, Abstr. — Publikacja dostępna online od: 2016-05-13
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 102514 |
|---|---|
| Data dodania do BaDAP | 2016-12-16 |
| Tekst źródłowy | URL |
| Rok publikacji | 2016 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | The Electronic Journal of Combinatorics |
Abstract
A locally irregular graph is a graph whose adjacent vertices have distinct degrees. We say that a graph G can be decomposed into k locally irregular subgraphs if its edge set may be partitioned into k subsets each of which induces a locally irregular subgraph in G. It has been conjectured that apart from the family of exceptions which admit no such decompositions, i.e., odd paths, odd cycles and a special class of graphs of maximum degree 3, every connected graph can be decomposed into 3 locally irregular subgraphs. Using a combination of a probabilistic approach and some known theorems on degree constrained subgraphs of a given graph, we prove this to hold for graphs of minimum degree at least 10(10). This problem is strongly related to edge colourings distinguishing neighbours by the pallets of their incident colours and to the 1-2-3 Conjecture. In particular, the contribution of this paper constitutes a strengthening of a result of Addario-Berry, Aldred, Dalal and Reed [J. Combin. Theory Ser. B 94 (2005) 237-244].