Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.05252 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- Let $G$ be a graph of order $n$, maximum degree at most $Δ$, and no component of order $2$. Inspired by the famous 1-2-3-conjecture, Bensmail, Marcille, and Orenga define a proper pushing scheme of $G$ as a function $ρ:V(G)\to\mathbb{N}_0$ for which $$σ:V(G)\to\mathbb{N}_0:u\mapsto \left(1+ρ(u)\right)d_G(u)+\sum_{v\in N_G(u)}ρ(v)$$ is a vertex coloring, that is, adjacent vertices receive different values under $σ$. They show the existence of a proper pushing scheme $ρ$ with $\max\{ ρ(u):u\in V(G)\}\leq Δ^2$ and conjecture that this upper bound can be improved to $Δ$. We show their conjecture for cubic graphs and regular bipartite graphs. Furthermore, we show the existence of a proper pushing scheme $ρ$ with $\sum_{u\in V(G)}ρ(u)\leq \left(2Δ^2+Δ\right)n/6$.