Szczegóły publikacji
Opis bibliograficzny
Decomposability of graphs into subgraphs fulfilling the $1–2–3$ Conjecture / Julien Bensmail, Jakub PRZYBYŁO // Discrete Applied Mathematics ; ISSN 0166-218X. — 2019 — vol. 268, s. 1–9. — Bibliogr. s. 8–9, Abstr. — Publikacja dostępna online od: 2019-05-10
Autorzy (2)
- Bensmail Julien
- AGHPrzybyło Jakub
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 125726 |
|---|---|
| Data dodania do BaDAP | 2020-01-12 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.dam.2019.04.011 |
| Rok publikacji | 2019 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Applied Mathematics |
Abstract
The well-known 1-2-3 Conjecture asserts that the edges of every graph without isolated edges can be weighted with 1, 2 and 3 so that adjacent vertices receive distinct weighted degrees. This is open in general. We prove that every d-regular graph, d >= 2, can be decomposed into at most 2 subgraphs (without isolated edges) fulfilling the 1-2-3 Conjecture if d is not an element of {10, 11, 12, 13, 15, 17}, and into at most 3 such subgraphs in the remaining cases. Additionally, we prove that in general every graph without isolated edges can be decomposed into at most 24 subgraphs fulfilling the 1-2-3 Conjecture, improving the previously best upper bound of 40. Both results are partly based on applications of the Lovasz Local Lemma. (C) 2019 Elsevier B.V. All rights reserved.
