EUVIMEDEUVIMED entdecken
Crossref

Coloring by pushing vertices

Dieter Rautenbach, Laurin Schwartze, Florian Werner

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →