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\).
We consider finite, simple, and undirected graphs and use standard terminology. For a graph \(G\), let \(V(G)\) denote the vertex set of \(G\) and let \(E(G)\) denote the edge set of \(G\). For a vertex \(u\) of \(G\), let \(N_G(u)\) denote the neighborhood of \(u\) in \(G\) and let \(d_G(u)\) denote the degree of \(u\) in \(G\). Let \(n(G)\), \(m(G)\), and \(\Delta(G)\) denote the order \(|V(G)|\), the size \(|E(G)|\), and the maximum degree \(\max\{d_G(u) : u \in V(G)\}\) of \(G\), respectively. A graph is nice if it has no component of order two. Let \(\mathbb{N}\) be the set of positive integers and let \(\mathbb{N}_{0} = \mathbb{N} \cup \{0\}\). For a non-negative integer \(k\), let \([k]\) be the set of all positive integers at most \(k\) and let \([k]_0 = \{0\} \cup [k]\).
Inspired by the famous 1-2-3-conjecture [1, 7], posed in 2004 by Karoński, Luczak, and Thomason [5] and solved in 2024 by Keusch [6], as well as by its wider context combining graph labeling and irregularity [3, 4], Bensmail, Marcille, and Orenga [2] recently proposed coloring graphs by so-called pushing schemes. The 1-2-3-conjecture states that the edges of every nice graph \(G\) can be labeled with 1, 2, and 3 in such a way that, for every two adjacent vertices, the sums of the labels of the incident edges are distinct, that is, there is a labeling \(\ell : E(G) \to [3]\) such that \[\label{eq1} \sum\limits_{w\in N_G(u)} \ell(uw) \neq \sum\limits_{w\in N_G(v)} \ell(vw) \text{ for every edge } uv \text{ of } G. \tag{1}\]
Now, Bensmail, Marcille, and Orenga consider a setting where the label \(\ell(e)\) of each edge \(e=uv\) arises by pushing the incident vertices \(u\) and \(v\) a certain number of times. More precisely, pushing \(\rho(u)\) times the vertex \(u\) and \(\rho(v)\) times the vertex \(v\) results in the edge label \(\ell(e)=1+\rho(u)+\rho(v)\). They call a function \[\rho : V(G) \to \mathbb{N}_{0},\] assigning a pushing value \(\rho(u)\) to every vertex \(u\) of \(G\) a proper pushing scheme of \(G\) if (1) holds for \(\ell(e)=1+\rho(u)+\rho(v)\) or, equivalently, if \[\label{eq2} \sigma(u) \neq \sigma(v) \text{ for every edge } uv \text{ of } G, \tag{2}\] where \[\label{eq3} \sigma : V(G) \to \mathbb{N}_{0} : u \mapsto (1+\rho(u)) d_G(u) + \sum\limits_{v\in N_G(u)} \rho(v), \tag{3}\] that is, the function \(\sigma : V(G) \to \mathbb{N}_{0}\) derived from \(\rho\) is a vertex coloring of \(G\). Unless stated otherwise, whenever we consider functions \(\rho\) and \(\sigma\) defined on the vertex set of some graph, they are related as in (3).
For a nice graph \(G\), Bensmail et al. [2] define \[P^1(G)=\min \left\{\max_{u\in V(G)} \rho(u) : \rho \text{ is a proper pushing scheme of } G\right\},\] and \[P^t(G)=\min \left\{\sum\limits_{u\in V(G)} \rho(u) : \rho \text{ is a proper pushing scheme of } G\right\}.\]
The definitions immediately imply \[\label{eq4} P^1(G) \leq P^t(G) \leq P^1(G)n(G). \tag{4}\]
Bensmail et al. [2] show \[\label{eq5} P^1(G) \leq \Delta(G)^2, \tag{5}\] and conjecture \[\label{eq6} P^1(G) \leq \Delta(G). \tag{6}\]
In view of (4), the inequality (5) implies \[\label{eq7} P^t(G) \leq \Delta(G)^2 n(G), \tag{7}\] and the conjecture (6) motivates the weaker conjecture \[\label{eq8} P^t(G) \leq \Delta(G)n(G). \tag{8}\]
Bensmail et al. [2] determine \(P^1\) for complete graphs, complete bipartite graphs, paths, trees, cycles, and cacti. The also show that deciding, for a given nice graph \(G\), whether \(P^1(G) \leq 1\) is NP-complete, and they also establish the hardness of \(P^t\).
Postponing all proofs and some statements to the next section, we now discuss our main contributions. Our first main result verifies conjecture (6) for cubic graphs.
Theorem 1.1. If \(G\) is a cubic graph, then \(P^1(G) \leq 3\).
We also establish conjecture (6) for regular bipartite graphs, see Proposition 2.1 below.
The proof of (5) in [2] relies on a natural greedy algorithm, which we explain in the next section. Our second main result improves (7) and is based on the greedy algorithm and the probabilistic first-moment method.
Theorem 1.2. If \(G\) is a nice graph of order \(n\) and maximum degree at most \(\Delta\), then the greedy algorithm applied to some linear ordering of the vertices of \(G\) yields a proper pushing scheme \(\rho : V(G) \to \mathbb{N}_{0}\) with \[P^t(G) \leq \sum\limits_{u\in V(G)} \rho(u) \leq \sum\limits_{u\in V(G)} \frac{1}{6}d_G(u)(2d_G(u)+1) \leq \frac{n\Delta(2\Delta+1)}{6}.\]
Our computational experiments indicate that the greedy algorithm is much better than expressed by (5) or Theorem 1.2 at least on average. In fact, executing the algorithm on all 4-regular graphs of order at most 15 and considering few random orderings for each of these graphs, the greedy algorithm is strong enough to establish conjecture (6) for these graphs. The next section contains two further minor results both pointing to possible improvements of (the analysis of) the greedy algorithm.
We immediately proceed to the:
Proof of Theorem 1.1. Clearly, we may assume that \(G\) is connected. If \(G=K_4\), then \(P^1(G)=3\) (cf. Observation 3.2 in [2]). Hence, we may assume that \(G\neq K_4\), and Brooks’ Theorem implies that \(G\) has chromatic number at most 3. Consider a three coloring of \(G\) with (possibly empty) color classes \(X\), \(Y\), and \(Z\), where the coloring is chosen in such a way that \(|Z|\) is as large as possible and, subject to this condition, \(|Y|\) is as large as possible. It follows that every vertex in \(X\) has a neighbor in \(Y\) and a neighbor in \(Z\), and that every vertex in \(Y\) has a neighbor in \(Z\). Let \(Y'\) be the set of vertices in \(Y\) that have a neighbor in \(X\), and let \(Y'' = Y \setminus Y'\). Note that the vertices in \(Y''\) have all their neighbors in \(Z\). Let \(Z'\) be the set of vertices in \(Z\) that have a neighbor in \(X\) or \(Y'\), and let \(Z''=Z\setminus Z'\). Note that the vertices in \(Z''\) have all their neighbors in \(Y''\). Let \(Y_0\) be the set of vertices in \(Y''\) that have no neighbor in \(Z''\), and let \(Y''' = Y'' \setminus Y_0\). Altogether,
every vertex in \(X\) has a neighbor in \(Y'\) and a neighbor in \(Z'\) but no neighbor in \(Y''\cup Z''\),
every vertex in \(Y'\) has a neighbor in \(X\) and a neighbor in \(Z'\) but no neighbor in \(Z''\),
every vertex in \(Y_0\) has all its neighbors in \(Z'\),
every vertex in \(Y'''\) has all its neighbors in \(Z\) and at least one neighbor in \(Z''\),
every vertex in \(Z'\) has a neighbor in \(X\) or \(Y'\), and
every vertex in \(Z''\) has all its neighbors in \(Y'''\).
For \(i\in\mathbb{N}\), let \(D_i=\{u\in Y'''\cup Z'' : \mathop{\mathrm{dist}}_G(u,Z')=i\}\). Note that \(\bigcup_{i\in\mathbb{N}}D_{2i-1}=Y'''\), \(\bigcup_{i\in\mathbb{N}}D_{2i}=Z''\), every vertex in \(D_1\) has a neighbor in \(D_2\), and every vertex in \(D_i\) for some \(i\geq 2\) has a neighbor in \(D_{i-1}\).
In order to complete the proof, we show that \[\rho : V(G) \to [3]_0 : u \mapsto \begin{cases} 0, & \text{if } u\in X\cup\displaystyle\bigcup_{i\in\mathbb{N}}D_{3i-2},\\[0.3em] 1, & \text{if } u\in Y',\\[0.3em] 2, & \text{if } u\in \displaystyle\bigcup_{i\in\mathbb{N}}D_{3i-1}, \text{ and}\\[0.3em] 3, & \text{if } u\in Y_0\cup Z'\cup\displaystyle\bigcup_{i\in\mathbb{N}}D_{3i}, \end{cases}\] is a proper pushing scheme.
See Figure 1 for an illustration.
In fact, the function \(\sigma\) as in (3) satisfies \[\sigma(u) \in \begin{cases} \{8,10\}, & \text{if } u\in X,\\ \{9,12\}, & \text{if } u\in Y',\\ \{21\}, & \text{if } u\in Y_0,\\ \{12,13,\ldots,19\}, & \text{if } u\in Z',\\ \{10,11\}, & \text{if } u\in D_1,\\ \{10,11,12\}, & \text{if } u\in \displaystyle\bigcup_{i\in\mathbb{N}}D_{3i+1},\\ \{9,12,15\}, & \text{if } u\in \displaystyle\bigcup_{i\in\mathbb{N}}D_{3i-1}, \text{ and}\\ \{14,16,18\}, & \text{if } u\in \displaystyle\bigcup_{i\in\mathbb{N}}D_{3i}. \end{cases}\]
Furthermore, if \(\sigma(u)=12\) for some vertex \(u\in Z'\), then \(u\) has no neighbor in \(Y'\), and, if \(\sigma(u)=12\) for some vertex \(u\in \bigcup_{i\in\mathbb{N}}D_{3i+1}\), then \(u\) has all its neighbors in \(\bigcup_{i\in\mathbb{N}}D_{3i}\). It follows that \(\sigma\) is a vertex coloring of \(G\), which completes the proof. ◻
The above proof strongly exploits that the considered graphs are regular. A simple variation of this proof yields conjecture (6) for regular bipartite graphs. It seems much harder to show the conjecture for subcubic graphs.
Proposition 2.1. If \(G\) is a \(\Delta\)-regular bipartite graph for some \(\Delta\geq 4\), then \(P^1(G)\leq \Delta\).
Proof. Clearly, we may assume that \(G\) is connected. Let \(r\) be any vertex of \(G\). Let \(D_i=\{u\in V(G): \mathop{\mathrm{dist}}_G(u,r)=i\}\) for \(i\in\mathbb{N}_{0}\). Since each of the sets \(D_i\) is contained in one of the two partite sets of \(G\), these sets are independent. Furthermore, if \(|i-j|\geq 2\), then there is no edge between \(D_i\) and \(D_j\). Hence, the sets \(C_j=\{u\in V(G): \mathop{\mathrm{dist}}_G(u,r)\equiv j \mod 3\}\) for \(j\in\{0,1,2\}\) are independent.
In order to complete the proof, we show that \[\rho : V(G) \to [\Delta]_0 : u \mapsto \begin{cases} \Delta, & \text{if } u\in C_0,\\ 1, & \text{if } u\in C_1, \text{ and}\\ 0, & \text{if } u\in C_2, \end{cases}\] is a proper pushing scheme.
Let \(u\) be a vertex such that \(\mathop{\mathrm{dist}}_G(u,r)\geq 1\). Let \(u\in C_k\). Since all neighbors of \(u\) are in \(C_{(k-1) \mod 3}\cup C_{(k+1) \mod 3}\) and \(u\) has at least one neighbor in \(C_{(k-1) \mod 3}\), we obtain \[\sigma(u) \in \begin{cases} \{\Delta^2+\Delta+k_0 : k_0\in[\Delta-1]_0\}, & \text{if } u\in C_0,\\ \{2\Delta+k_1\Delta : k_1\in[\Delta]\}, & \text{if } u\in C_1, \text{ and}\\ \{\Delta+k_2+\Delta(\Delta-k_2) : k_2\in[\Delta]\}, & \text{if } u\in C_2. \end{cases}\]
Note that \(r\in C_0\) and \(\sigma(r)=\Delta^2+2\Delta\). Furthermore, if \(u\) is a neighbor of \(r\), then \(u\in C_1\) and \(\sigma(u)=3\Delta\neq \sigma(r)\). Now, let \(uv\) be an edge of \(G\) that is not incident with \(r\). By symmetry, we may assume that \(u\in C_i\) and \(v\in C_{(i+1) \mod 3}\). If \(i=0\), then \(\sigma(u)\not\equiv 0 \mod \Delta\), because \(u\in C_0\) has \(k_0\geq 1\) neighbors in \(C_1\), and \(\sigma(v)\equiv 0 \mod \Delta\). If \(i=1\), then \(2\Delta<\sigma(u)\equiv 0 \mod \Delta\) and either \(\sigma(v)\not\equiv 0\) \(\mod\ \Delta\) (for \(k_2\neq \Delta\)) or \(\sigma(v)=2\Delta\) (for \(k_2=\Delta\)). If \(i=2\), then \(\sigma(u)\leq \Delta^2+1\) and \(\sigma(v)\geq \Delta^2+\Delta\). In all three cases, we obtain \(\sigma(u)\neq \sigma(v)\), which completes the proof. ◻
For the proof of Theorem 1.2, we explain the greedy algorithm from [2]. In our exposition we slightly deviate from [2] in the way we handle vertices of degree 1; this deviation is not essential yet simpler: Let \(G\) be a nice graph of order \(n\) and maximum degree at most \(\Delta\). Let \(u_1,\ldots,u_n\) be a linear ordering of the vertices of \(G\). The greedy algorithm deterministically produces a sequence \(\rho_0,\rho_1,\ldots,\rho_n\) of functions \(\rho_i : V(G) \to \mathbb{N}_{0}\) such that, for every \(i\in [k]_0\), the following two properties hold:
Property \(P_i^{(1)}\): \(\rho_i(u_j)=0\) for every \(j\in [n]\setminus[i]\).
Property \(P_i^{(2)}\): For \[\sigma_i : V(G) \to \mathbb{N}_{0} : u \mapsto (1+\rho_i(u))d_G(u)+\sum\limits_{v\in N_G(u)}\rho_i(v),\] there is no edge \(u_j u_k\) with \(j,k\in[i]\) and \(\sigma_i(u_j)=\sigma_i(u_k)\), that is, condition (2) referring to all edges of \(G\) is required only for the edges with both endpoints in \(\{u_1,\ldots,u_i\}\).
By \(P_0^{(1)}\), we have \(\rho_0(u)=0\) for every vertex \(u\) of \(G\) and the condition \(P_0^{(2)}\) is void. By \(P_n^{(2)}\), we have that \(\rho_n\) is a proper pushing scheme.
Now, suppose that, for some \(i\in[n]\), the function \(\rho_{i-1}\) satisfies \(P_{i-1}^{(1)}\) and \(P_{i-1}^{(2)}\). Note that, in particular, we have \(\rho_{i-1}(u_i)=0\). Let \[\rho_i(u_j)= \begin{cases} \rho_{i-1}(u_j) & \text{for } j\in[n]\setminus\{i\}, \text{ and}\\ s & \text{for } j=i, \end{cases}\] where \(s\) is the smallest non-negative integer such that the function \(\rho_i\) satisfies \(P_i^{(2)}\); note that \(P_i^{(1)}\) holds by construction. The key observation of Bensmail et al. [2] is that a valid choice for \(s\) exists and that, in fact, it satisfies \(s\leq \Delta^2\). If \(u_i\) has degree at most 1, then \(s=0\) is a valid choice, because \(G\) is nice, that is, the functions \(\rho_i\) and \(\rho_{i-1}\) are the same. If \(u_i\) has degree at least 2, then
for every \(j\in[i-1]\) with \(u_i u_j\in E(G)\), the condition “\(\sigma_i(u_i)\neq \sigma_i(u_j)\)” excludes at most one non-negative integer as a valid choice for \(s\), and
for every two distinct \(j,k\in[i-1]\) with \(u_i u_j, u_j u_k\in E(G)\) and \(u_i u_k\notin E(G)\), the condition “\(\sigma_i(u_j)\neq \sigma_i(u_k)\)” excludes at most one non-negative integer as a valid choice for \(s\).
Since all other relevant edges are not affected by changing the value at \(u_i\), this implies that \[\label{eq9} \rho_n(u_i)=\rho_i(u_i)\in \left[s_i^{(1)}+s_i^{(2)}\right]_0, \tag{9}\] where
\(s_i^{(1)}\) is the number of \(j\) with \(j\in[i-1]\) and \(u_i u_j\in E(G)\), and
\(s_i^{(2)}\) is the number of \((j,k)\) with \(j,k\in[i-1]\) and \(u_i u_j, u_j u_k\in E(G)\) and \(u_i u_k\notin E(G)\).
Note that the set \(\left[s_i^{(1)}+s_i^{(2)}\right]_0\) contains \(1+s_i^{(1)}+s_i^{(2)}\) elements, which is at least one more than the number of excluded valid choices. Since \(s_i^{(1)}\leq d_G(u_i)\leq \Delta\) and \[s_i^{(2)}\leq \sum\limits_{v\in N_G(u_i)}(d_G(v)-1)\leq \Delta(\Delta-1),\] we have \(s_i^{(1)}+s_i^{(2)}\leq \Delta^2\), which implies (5).
We are now in a position to show our second main result.
Proof of Theorem 1.2. Consider the application of the above greedy algorithm to a linear ordering \(u_1,\ldots,u_n\) of the vertices of \(G\) that is chosen uniformly at random. For \(i\in[n]\), let \(d_i^-\) be the number of neighbors \(u_j\) of \(u_i\) with \(j<i\), and let \(d_i^+=d_G(u_i)-d_i^-\). By the definitions of \(s_i^{(1)}\) and \(s_i^{(2)}\), double-counting implies \[\sum\limits_{i=1}^n s_i^{(1)}=\sum\limits_{j=1}^n d_j^+ \quad\text{and}\quad \sum\limits_{i=1}^n s_i^{(2)}\leq \sum\limits_{j=1}^n\left(d_j^- d_j^+ + \binom{d_j^+}{2}\right).\]
Using (9) and the linearity of expectation, we obtain \[\begin{aligned} P^t(G) &\leq \mathbb{E}\left[\sum\limits_{i=1}^n \left(s_i^{(1)}+s_i^{(2)}\right)\right] \\ &\leq \mathbb{E}\left[\sum\limits_{j=1}^n \left(d_j^+ + d_j^-d_j^+ + \binom{d_j^+}{2}\right)\right]\\ &= \sum\limits_{j=1}^n \mathbb{E}\left[d_j^+ + d_j^-d_j^+ + \binom{d_j^+}{2}\right]. \end{aligned}\]
The uniform random choice of the linear ordering implies that \(\mathbb{E}\left[d_j^+ + d_j^-d_j^+ + \binom{d_j^+}{2}\right]\) equals \[\frac{1}{d_G(u_j)+1}\sum\limits_{d^-=0}^{d_G(u_j)} \left(\left(d_G(u_j)-d^-\right)+d^-\left(d_G(u_j)-d^-\right)+\binom{d_G(u_j)-d^-}{2}\right),\] because all \(d_G(u_j)+1\) values in \(\{0,\ldots,d_G(u_j)\}\) are equally likely for \(d^-\) and \(d_j^+\) equals \(d_G(u_j)-d_j^-\). It follows that \[\begin{aligned} P^t(G) \leq {} & \sum\limits_{j=1}^n \left(\frac{1}{d_G(u_j)+1}\sum\limits_{d^-=0}^{d_G(u_j)} \left(\left(d_G(u_j)-d^-\right)+d^-\left(d_G(u_j)-d^-\right)+\binom{d_G(u_j)-d^-}{2}\right)\right)\\ ={} & \sum\limits_{j=1}^n \frac{1}{6}d_G(u_j)(2d_G(u_j)+1), \end{aligned}\] which completes the proof. ◻
For a cubic graph \(G\) of order \(n\), Theorem 1.2 implies \(P^t(G)\leq 3.5n\), which is actually weaker than the bound \(P^t(G)\leq 3n\) implied by (4) and Theorem 1.1. Executing the greedy algorithm on all cubic graphs \(G\) of order \(n\leq 20\) yields proper pushing schemes \(\rho : V(G)\to\mathbb{N}_{0}\) where \(\sum\limits_{u\in V(G)}\rho(u)\) behaves roughly like \(5n/8\) on average, that is, much better than guaranteed by Theorem 1.2. Similarly, executing the greedy algorithm on all 4-regular graphs \(G\) of order \(n\leq 15\) yields proper pushing schemes \(\rho\) where \(\sum\limits_{u\in V(G)}\rho(u)\) behaves roughly like \(2n/3\) on average.
The following two propositions point to possible improvements of (the analysis of) the greedy algorithm. Recall that the girth of a graph is the length of a shortest cycle.
Proposition 2.2. If \(G\) is a cubic graph of girth at least 5, then the greedy algorithm applied to some linear ordering of the vertices of \(G\) yields a proper pushing scheme \(\rho : V(G)\to\mathbb{N}_{0}\) with \[\sum\limits_{u\in V(G)} \rho(u)\leq (3.5-23/840)n.\]
Proof. As in the proof of Theorem 1.2, consider the application of the greedy algorithm to a linear ordering \(u_1,\ldots,u_n\) of the vertices of \(G\) that is chosen uniformly at random. For \(i\in[n]\), let \(g_i\) be the final pushing value assigned to \(u_i\) by the greedy algorithm, that is, \(g_i=\rho_i(u_i)=\rho_n(u_i)\). Theorem 1.2 relies on the estimate \(g_i\leq s_i:=s_i^{(1)}+s_i^{(2)}\). In order to quantify the improvement of this estimate, we define \(t_1,\ldots,t_n\) as follows:
Initialize \(t_i\) as 0 for every \(i\in[n]\). For \(i\) from 1 up to \(n\) proceed as follows: If \(u_i\) has no neighbor \(u_j\) with \(j>i\), then increase \(t_i\) by \(s_i-g_i\). Otherwise, let \(u_j\) be the neighbor of \(u_i\) with largest index \(j\), increase \(t_i\) by \((s_i-g_i)/4\) and \(t_j\) by \(3(s_i-g_i)/4\).
Clearly, we have \(\sum\limits_{i=1}^n g_i=\sum\limits_{i=1}^n s_i-\sum\limits_{i=1}^n t_i\). By linearity of expectation, we have \[\label{eq10} \mathbb{E}\left[\sum\limits_{i=1}^n g_i\right]=\mathbb{E}\left[\sum\limits_{i=1}^n s_i\right]-\mathbb{E}\left[\sum\limits_{i=1}^n t_i\right]\leq 3.5n-\sum\limits_{i=1}^n\mathbb{E}[t_i]. \tag{10}\]
The assumptions that \(G\) is cubic and of girth at least 5 simplify the estimation of \(\mathbb{E}[t_i]\).
Let \(i\in[n]\). Let \(u=u_i\), let \(N_G(u)=\{v_1,v_2,v_3\}\), and, for \(i\in[3]\), let \(N_G(v_i)=\{u,v_{i,1},v_{i,2}\}\). Since \(G\) has girth at least 5, the set \(U=\{u,v_1,v_2,v_3,v_{1,1},v_{1,2},v_{2,1},v_{2,2},v_{3,1},v_{3,2}\}\) contains exactly 10 distinct vertices. Restricting the linear ordering \(u_1,\ldots,u_n\) to \(U\) yields a permutation \(\pi\) from \(S_U\) and, since the linear ordering is chosen uniformly at random, each of the \(10!\) permutations in \(S_U\) is equally likely to be the restriction. Note that \(s_i\) is completely determined by \(\pi\).
There is a set \(S_1\) of exactly \(\frac{3\cdot 2!\cdot 2!}{6!}\cdot 10!\) permutations in \(S_U\), corresponding to linear orderings of \(U\), in which
exactly one neighbor \(v\) of \(u\) comes before \(u\) and
the two neighbors of \(v\) that are distinct from \(u\) both come before \(v\).
There is a set \(S_2\) of exactly \(\frac{3\cdot 2!\cdot 2!}{6!}\cdot 10!\) permutations in \(S_U\) in which
exactly one neighbor \(v\) of \(u\) comes before \(u\),
exactly one of the two neighbors of \(v\) that are distinct from \(u\) comes before \(v\), and
the other neighbor of \(v\) that is distinct from \(u\) comes after \(v\) and before \(u\).
There is a set \(S_3\) of exactly \(3!\cdot 6!\) permutations in \(S_U\) in which
all three neighbors \(v_1\), \(v_2\), and \(v_3\) of \(u\) come before \(u\) and
all six vertices \(v_{1,1}\), \(v_{1,2}\), \(v_{2,1}\), \(v_{2,2}\), \(v_{3,1}\), and \(v_{3,2}\) come after \(u\).
If \(\pi\in S_U\setminus(S_1\cup S_2\cup S_3)\), then \(t_i\geq 0\). Now, let \(\pi\in S_1\). Let \(u_j\) be the unique neighbor of \(u_i\) with \(j<i\). Note that \(s_i=3\) and \(s_j\geq 2\). If \(\sigma_{i-1}(u_j)>3\), then \(g_i=0\), which implies \(t_i\geq(s_i-g_i)/4=3/4\). If \(\sigma_{i-1}(u_j)=3\), then \(g_j=0\), which implies \(t_i\geq 3(s_j-g_j)/4\geq 3/2\). Altogether, we obtain \(t_i\geq 3/4\). Next, let \(\pi\in S_2\). Let \(u_j\) be the unique neighbor of \(u_i\) with \(j<i\). Note that \(s_i=3\) and \(s_j\geq 1\). If \(\sigma_{i-1}(u_j)>3\), then \(g_i=0\), which implies \(t_i\geq(s_i-g_i)/4=3/4\). If \(\sigma_{i-1}(u_j)=3\), then \(g_j=0\), which implies \(t_i\geq3(s_j-g_j)/4\geq 3/4\). Altogether, we obtain \(t_i\geq 3/4\). Finally, let \(\pi\in S_3\). In this case \(s_i=3\) and \(g_i=1\), which implies \(t_i\geq s_i-g_i=2\).
By the uniform random choice of the linear ordering, we obtain \[\begin{aligned} \mathbb{E}[t_i] &\geq \frac{1}{10!}\left(\frac{3}{4}|S_1|+\frac{3}{4}|S_2|+2|S_3|\right)\\ &\geq \frac{1}{10!}\left(\frac{3}{4}\cdot\frac{3\cdot2!\cdot2!}{6!}\cdot10!+\frac{3}{4}\cdot\frac{3\cdot2!\cdot2!}{6!}\cdot10!+2\cdot3!\cdot6!\right)\\ &=23/840, \end{aligned}\] and (10) completes the proof. ◻
It is possible to generalize Proposition 2.2 to larger regularities and also to graphs of any girth. Provided that \(G\) is nice, connected, and of maximum degree at most \(\Delta\) but not \(\Delta\)-regular, Bensmail et al. [2] use a breadth-first search argument to show that \(P^1(G)\leq \Delta^2-\Delta\). Our final result also builds on their greedy algorithm.
Proposition 2.3. If \(G\) is a nice graph of maximum degree at most \(\Delta\), then \(P^1(G)\leq \Delta^2-1\).
Proof. By the argument of Bensmail et al. [2] mentioned just before Proposition 2.3, we may assume that \(G\) is connected and \(\Delta\)-regular. Since \(P^1(K_{\Delta,\Delta})=1\) (cf. Theorem 3.1 in [2]), we may assume that \(G\) is not \(K_{\Delta,\Delta}\). Let \(u_1,\ldots,u_n\) be a reverse breadth-first search ordering, that is, in particular, for every \(i\in[n-1]\), the vertex \(u_i\) has a neighbor \(u_j\) with \(j>i\). This implies that the function \(\rho_{n-1}:V(G)\to\mathbb{N}_{0}\) that is produced by the greedy algorithm and satisfies \(P_{n-1}^{(1)}\) and \(P_{n-1}^{(2)}\) only uses values in \([\Delta^2-\Delta]_0\). In particular, only the final vertex \(u_n\) may require \(\Delta^2\) pushes.
Let \(u=u_n\), let \(N_G(u)=\{v_1,\ldots,v_\Delta\}\), and, for every \(i\in[\Delta]\), let \(N_G(v_i)\\=\{u,v_{i,1},\ldots,v_{i,\Delta-1}\}\). Since \(G\) is not \(K_{\Delta,\Delta}\), we may assume that \(v_{1,1}\) is not adjacent to all vertices in \(N_G(u)\). In view of the desired statement, we may assume that \(\Delta^2\) is the only valid choice for \(\rho_n(u_n)\) within the set \([\Delta^2]_0\). More precisely, for every \(s\) in \([\Delta^2-1]_0\), there is an edge \(e(s)\) incident with a neighbor of \(u\), say \(e(s)=xy\), such that setting \(\rho_n(u)\) to \(s\) results in \(\sigma_n(x)=\sigma_n(y)\). Note that there are at most \(\Delta^2\) edges incident with neighbors of \(u\). It follows that \(u\) does not lie in a triangle, that the edge \(e(s)\) is unique for every \(s\in[\Delta^2-1]_0\), and that \(\{e(s):s\in[\Delta^2-1]_0\}\) is the set of all \(\Delta^2\) distinct edges that are incident with neighbors of \(u\). For \(i\in[\Delta]\) and \(j\in[\Delta-1]\), let \(s_i\) be such that \(e(s_i)=uv_i\) and let \(s_{i,j}\) be such that \(e(s_{i,j})=v_i v_{i,j}\).
The set \([\Delta^2-\Delta]_0\cup\{\Delta^2-\Delta+1\}\) contains a value \(t'\) distinct from \(t=\rho_{n-1}(v_1)\) such that changing within \(\rho_{n-1}\) the value of \(v_1\) from \(t\) to \(t'\) yields a function \(\rho'_{n-1}\) that satisfies \(P_{n-1}^{(1)}\) and \(P_{n-1}^{(2)}\). In view of the desired statement, we may again assume that, for every \(s'\) in \([\Delta^2-1]_0\), there is an edge \(e'(s')\) incident with a neighbor of \(u\), say \(e'(s')=xy\), such that changing within \(\rho'_{n-1}\) the value of \(u\) from 0 to \(s'\) yields a function \(\rho'_n\) with \(\sigma'_n(x)=\sigma'_n(y)\), where \(\sigma'_n\) is derived from \(\rho'_n\) in the obvious way. As before, the edge \(e'(s')\) is unique for every \(s'\in[\Delta^2-1]_0\) and \(\{e'(s') : s'\in[\Delta^2-1]_0\}\) is the set of all \(\Delta^2\) distinct edges that are incident with neighbors of \(u\). For \(i\in[\Delta]\) and \(j\in[\Delta-1]\), let \(s'_i\) be such that \(e'(s'_i)=uv_i\) and let \(s'_{i,j}\) be such that \(e'(s'_{i,j})=v_i v_{i,j}\).
Note that \[\begin{aligned} \label{eq11} [\Delta^2-1]_0 &= \{s'_i : i\in[\Delta]\}\cup\{s'_{i,j}: i\in[\Delta] \text{ and } j\in[\Delta-1]\}\notag\\ &= \{s_i : i\in[\Delta]\}\cup\{s_{i,j}: i\in[\Delta] \text{ and } j\in[\Delta-1]\}. \end{aligned} \tag{11}\]
Since \(\rho'_{n-1}\) and \(\rho_{n-1}\) only differ at \(v_1\), if follows, for \(\alpha=t'-t=\rho'_{n-1}(v_1)-\rho_{n-1}(v_1)\), that
\(s'_1=s_1+\alpha\),
\(s'_i=s_i-\frac{\alpha}{\Delta-1}\) for every \(i\in[\Delta]\setminus\{1\}\), and
\(s'_{1,j}=s_{1,j}-(\Delta-1)\alpha\) for every \(j\in[\Delta-1]\).
Now, let \(i\in[\Delta]\setminus\{1\}\) and \(j\in[\Delta-1]\). If \(v_{i,j}\) is not adjacent to \(v_1\), then \(s'_{i,j}=s_{i,j}\), and, if \(v_{i,j}\) is adjacent to \(v_1\), then \(s'_{i,j}=s_{i,j}+\alpha\). Note that \(\sum\limits_{i=1}^{\Delta}(s'_i-s_i)=\alpha-\frac{\alpha}{\Delta-1}(\Delta-1)=0\). Furthermore, if \(v_{1,\ell}\) has exactly \(k\) neighbors in \(N_G(u)\), then the sum of \(s'_{i,j}-s_{i,j}\) over all edges \(v_i v_{i,j}\) with \(v_{i,j}=v_{1,\ell}\) equals \(-(\Delta-1)\alpha+(k-1)\alpha=-(\Delta-k)\alpha\). Since \(v_{1,1}\) is not adjacent to all vertices in \(N_G(u)\), it follows that \[\sum\limits_{i=1}^{\Delta}\left(s'_i+\sum\limits_{j=1}^{\Delta-1}s'_{i,j}\right) \neq \sum\limits_{i=1}^{\Delta}\left(s_i+\sum\limits_{j=1}^{\Delta-1}s_{i,j}\right).\] This contradicts (11), which completes the proof. ◻
There is a weakness in the analysis of the greedy algorithm that we have not been able to overcome: As explained before (9), at most \(s_i^{(1)}+s_i^{(2)}\) of the \(s_i^{(1)}+s_i^{(2)}+1\) elements in \(\left[s_i^{(1)}+s_i^{(2)}\right]_0\) are excluded by the required conditions. Now, the analysis of the greedy algorithm pessimistically assumes that the smallest non-excluded element of that set is its maximum, which seems unlikely as least on average.