Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2504.21452 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910930877546496 |
|---|---|
| author | Bensmail, Julien Martins, Beatriz Tang, Chaoliang |
| author_facet | Bensmail, Julien Martins, Beatriz Tang, Chaoliang |
| contents | In a recent work, Keusch proved the so-called 1-2-3 Conjecture, raised by Karoński, Łuczak, and Thomason in 2004: for every connected graph different from $K_2$, we can assign labels~$1,2,3$ to the edges so that no two adjacent vertices are incident to the same sum of labels. Despite this significant result, several problems close to the 1-2-3 Conjecture in spirit remain widely open. In this work, we focus on the so-called 1-2 Conjecture, raised by Przybyło and Woźniak in 2010, which is a counterpart of the 1-2-3 Conjecture where labels~$1,2$ only can be assigned, and both vertices and edges are labelled. We consider both the 1-2 Conjecture in its original form, where adjacent vertices must be distinguished w.r.t.~their sums of incident labels, and variants for products and multisets. We prove some of these conjectures for graphs with bounded maximum degree (at most~$6$) and bounded maximum average degree (at most~$3$), going beyond earlier results of the same sort. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_21452 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | 1-2 Conjectures for Graphs with Low Degeneracy Properties Bensmail, Julien Martins, Beatriz Tang, Chaoliang Combinatorics In a recent work, Keusch proved the so-called 1-2-3 Conjecture, raised by Karoński, Łuczak, and Thomason in 2004: for every connected graph different from $K_2$, we can assign labels~$1,2,3$ to the edges so that no two adjacent vertices are incident to the same sum of labels. Despite this significant result, several problems close to the 1-2-3 Conjecture in spirit remain widely open. In this work, we focus on the so-called 1-2 Conjecture, raised by Przybyło and Woźniak in 2010, which is a counterpart of the 1-2-3 Conjecture where labels~$1,2$ only can be assigned, and both vertices and edges are labelled. We consider both the 1-2 Conjecture in its original form, where adjacent vertices must be distinguished w.r.t.~their sums of incident labels, and variants for products and multisets. We prove some of these conjectures for graphs with bounded maximum degree (at most~$6$) and bounded maximum average degree (at most~$3$), going beyond earlier results of the same sort. |
| title | 1-2 Conjectures for Graphs with Low Degeneracy Properties |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2504.21452 |