Coloring by Pushing Vertices

Abstract

Let $G$ be a graph of order $n$, maximum degree at most $\hat{I}”$, 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 $\ddot{I}:V(G)\to {\mathbb{N}}_0$ for which $$\ddot{I}ƒ:V(G)\to {\mathbb{N}}_0:u\mapsto \left(1+\ddot{I}(u)\right)d_G(u)+\sum _{v\in N_G(u)}\ddot{I}(v)$$ is a vertex coloring, that is, adjacent vertices receive different values under $\ddot{I}ƒ$. They show the existence of a proper pushing scheme $\ddot{I}$ with $\max \{\ddot{I}(u):u\in V(G)\}\le \hat{I}{”}^2$ and conjecture that this upper bound can be improved to $\hat{I}”$. We show their conjecture for cubic graphs and regular bipartite graphs. Furthermore, we show the existence of a proper pushing scheme $\ddot{I}$ with ${\sum }_{u\in V(G)}\ddot{I}(u)\le \left(2\hat{I}{”}^2+\hat{I}”\right)n/6$.