Decomposability of graphs into subgraphs fulfilling the 1-2-3 Conjecture - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2019

Decomposability of graphs into subgraphs fulfilling the 1-2-3 Conjecture

Résumé

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 not in {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 Lovász Local Lemma.
Fichier principal
Vignette du fichier
regular_decomposition_123_DAM_REVISED.pdf (292.4 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02288797 , version 1 (16-09-2019)

Identifiants

Citer

Julien Bensmail, Jakub Przybyƚo. Decomposability of graphs into subgraphs fulfilling the 1-2-3 Conjecture. Discrete Applied Mathematics, 2019, ⟨10.1016/j.dam.2019.04.011⟩. ⟨hal-02288797⟩
48 Consultations
190 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More