Given a complete undirected graph $K_n$, it's given a refinement algorithm that builds, at iteration $t$, a sorted partition $E^t$ of the edges and a sorted partition $V^t$ of the vertices by refining the partitions $E^{t-1}$ and $V^{t-1}$, calculated in the previous iteration, where the initial vertex partition is $V^0=\{V(G)\}$ (trivial partition) and the initial edge partition $E^0$ is input of the problem and can be any sorted partition.
The ingredients of the algorithm are:
If $k_x$ is the key of an element $x$, to refine a sorted partition $P=\left[P_1, \ldots, P_l\right]$ based on such keys, for each $P_i$, split $P_i$ in new parts by grouping its elements by key, sort the new parts by the key they represent, and replace $P_i$ by the new parts in the same order. If $x\in P_i$, we say $x$ has rank $i$.
Vectors used as keys are compared lexicographically.
Given a vertex $v$, its key at iteration $t$ is a vector of size $|E^{t-1}|$ where its $i$-th element is the degree of $v$ in $K_n[E^{t-1}_i]$.
Given edge $uv$, its key at turn $t$ is the 2-vector $[\min(r_u, r_v), \max(r_u, r_v)]$, where $r_u$ and $r_v$ are the ranks of $u$ and $v$ in $V^t$.
The algorithm is obvious now: turn $t$ is defined by refining $V^{t-1}$ using $E^{t-1}$ to calculate the vertex keys and so build $V^t$, and then refine $E^{t-1}$ using the refined $V^t$ to calculate the edge keys and so build $E^t$. If $V^{t-1}=V^t$ the algorithm stops and outputs $V^*\colon=V^t$.
I want to understand the properties of this algorithm better, so my question is:
- What are the necessary and sufficient conditions the initial edge partition $E^0$ must satisfy so that $|V^*|=n$ (so that $E^0$ finds a total order of the vertices using the algorithm above)?
It's obvious that if at any step $s$ of the algorithm all $K_n[E^s_i]$ are regular graphs of order $n$ then $|V^*|\lt n$.
The context is that I have millions of different such initial edge partitions and I want to "filter-out" as fast as possible all of those that will turn $V(G)$ into a total order, without having to know which total order that would be. This problem lead me to generalize it as the question I'm asking here, because I want to understand better the combinatorial properties of the problem.
I've tried to look in the existing literature but despite its similarity with other partition refinement and vertex-coloring algorithms, I haven't been able to find a description of my particular version.