Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.14253 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911233027866624 |
|---|---|
| author | Deng, Kecai Qiu, Hongyuan |
| author_facet | Deng, Kecai Qiu, Hongyuan |
| contents | For a simple graph $G=(V,E)$, a \emph{proper total weighting} is a mapping $w: V\cup E\rightarrow \mathbb R$ such that for every edge $uv\in E$, $w(u)+\sum_{e\ni u}w(e)\neq w(v)+\sum_{e\ni v}w(e)$. The graph $G$ is said $(2,2)$-\emph{choosable} if, for any list assignment $L$ that assigns to each $z$ in $V\cup E$ a set $L(z)$ of two real numbers, there exists a {proper total weighting} $w$ with $w(z)\in L(z)$ for every $z\in V\cup E$. Wong and Zhu, and independently Przybyło and Woźniak conjectured that every simple graph is $(2,2)$-choosable. This conjecture remains open.
For a set $\{a,b\}\subset \mathbb R$, its span is defined as $|b-a|$. We call a graph $G=(V,E)$ \emph{uniform-span} $(2,2)$-\emph{choosable} if, for any list assignment $L$ that assigns to every $z\in V\cup E$ a two-element list of a common span, there exists a {proper total weighting} respect to the assignment. In this paper, we present a novel lemma and perform comprehensive enhancements to our previous algorithm. These contributions enable us to prove that every graph is uniform-span $(2,2)$-choosable. This confirms the 1-2 conjecture in full generality, and provides supporting evidence for the $(2,2)$-choosable conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_14253 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Every graph is uniform-span $(2,2)$-choosable: Beyond the 1-2 conjecture Deng, Kecai Qiu, Hongyuan Combinatorics 05C15 For a simple graph $G=(V,E)$, a \emph{proper total weighting} is a mapping $w: V\cup E\rightarrow \mathbb R$ such that for every edge $uv\in E$, $w(u)+\sum_{e\ni u}w(e)\neq w(v)+\sum_{e\ni v}w(e)$. The graph $G$ is said $(2,2)$-\emph{choosable} if, for any list assignment $L$ that assigns to each $z$ in $V\cup E$ a set $L(z)$ of two real numbers, there exists a {proper total weighting} $w$ with $w(z)\in L(z)$ for every $z\in V\cup E$. Wong and Zhu, and independently Przybyło and Woźniak conjectured that every simple graph is $(2,2)$-choosable. This conjecture remains open. For a set $\{a,b\}\subset \mathbb R$, its span is defined as $|b-a|$. We call a graph $G=(V,E)$ \emph{uniform-span} $(2,2)$-\emph{choosable} if, for any list assignment $L$ that assigns to every $z\in V\cup E$ a two-element list of a common span, there exists a {proper total weighting} respect to the assignment. In this paper, we present a novel lemma and perform comprehensive enhancements to our previous algorithm. These contributions enable us to prove that every graph is uniform-span $(2,2)$-choosable. This confirms the 1-2 conjecture in full generality, and provides supporting evidence for the $(2,2)$-choosable conjecture. |
| title | Every graph is uniform-span $(2,2)$-choosable: Beyond the 1-2 conjecture |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2506.14253 |