Szczegóły publikacji
Opis bibliograficzny
Decomposability of regular graphs to 4 locally irregular subgraphs / Jakub PRZYBYŁO // Applied Mathematics and Computation ; ISSN 0096-3003. — 2024 — vol. 480 art. no. 128916, s. 1-10. — Bibliogr. s. 10, Abstr. — Publikacja dostępna online od: 2024-07-03
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 155022 |
|---|---|
| Data dodania do BaDAP | 2024-09-21 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.amc.2024.128916 |
| Rok publikacji | 2024 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Applied Mathematics and Computation |
Abstract
A locally irregular graph is a graph whose adjacent vertices have distinct degrees. It was conjectured that every connected graph is edge decomposable to 3 locally irregular subgraphs, unless it belongs to a certain family of exceptions, including graphs of small maximum degrees, which are not decomposable to any number of such subgraphs. Recently Sedlar and Škrekovski exhibited a counterexample to the conjecture, which necessitates a decomposition to (at least) 4 locally irregular subgraphs. We prove that every d-regular graph with d large enough, i.e. , is decomposable to 4 locally irregular subgraphs. Our proof relies on a mixture of a numerically optimized application of the probabilistic method and certain deterministic results on degree constrained subgraphs due to Addario-Berry, Dalal, McDiarmid, Reed, and Thomason, and to Alon and Wei, introduced in the context of related problems concerning irregular subgraphs.
