Coloring by pushing vertices
Ars Combinatoria · 17.06.2026 · 167 · 147-157
DOI: 10.61091/ars167-10 ↗Kurz gefasst
Fachartikel in der Zeitschrift Ars Combinatoria, online erschienen am 17.06.2026. Verfasst von Dieter Rautenbach und 2 weiteren Autor:innen.
Abstract (Originalsprache)
Let \(G\) be a graph of order \(n\), maximum degree at most \(\Delta\), 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 \(\rho : V(G) \to \mathbb{N}_{0}\) for which \[\sigma : V(G) \to \mathbb{N}_{0} : u \mapsto (1+\rho(u)) d_G(u) + \sum\limits_{v\in N_G(u)} \rho(v),\] is a vertex coloring, that is, adjacent vertices receive different values under \(\sigma\). They show the existence of a proper pushing scheme \(\rho\) with \(\max\{\rho(u) : u \in V(G)\} \leq \Delta^2\) and conjecture that this upper bound can be improved to \(\Delta\). We show their conjecture for cubic graphs and regular bipartite graphs. Furthermore, we show the existence of a proper pushing scheme \(\rho\) with \(\sum\limits_{u\in V(G)} \rho(u) \leq (2\Delta^2+\Delta)n/6\).
Zitieren
APA
Rautenbach, D., Schwartze, L., & Werner, F. (2026). Coloring by pushing vertices. Ars Combinatoria, 167, 147-157. https://doi.org/10.61091/ars167-10
Vancouver
Rautenbach D, Schwartze L, Werner F. Coloring by pushing vertices. Ars Combinatoria. 2026;167:147-157. doi:10.61091/ars167-10
BibTeX
@article{Rautenbach2026,
author = {Rautenbach, Dieter and Schwartze, Laurin and Werner, Florian},
title = {Coloring by pushing vertices},
journal = {Ars Combinatoria},
year = {2026},
volume = {167},
pages = {147--157},
doi = {10.61091/ars167-10}
}
EUVIMED