How many distinct labels do you need to label a graph’s vertices so that any two vertices sharing the same label are always “separated” by a vertex with a higher label? This is the vertex ranking problem. We build Wolfram Language functionality to construct all rankings of a given graph using a given number of labels, apply this function to a range of graphs, and visualize the results.
Vertex Rankings of Graphs
Vertex Rankings of Graphs
A vertex ranking of a graph G is a labeling of its vertices with positive integers such that for any two vertices with the same label, every path between them contains at least one vertex with a strictly larger label. The idea is that same-labeled vertices must always be “screened” by something taller. A k-ranking restricts the labels to {1, 2, ..., k}. The ranking number χr(G) is the minimum k achieving a valid ranking; it satisfies χr(G) ≥ χ(G) (the chromatic number), since every ranking is also a proper coloring. Vertex rankings arise naturally in the study of graph separators and tree-width, appearing in scheduling, VLSI layout, and parallel computation where hierarchical decompositions are key.
No Wolfram Language functions exist specifically for vertex ranking, so our computational challenge is to build a function to perform the following task: given a graph G and an integer k, list every possible k-ranking of G. Our algorithm relies on the following observation: a vertex labelling of a graph is a k-ranking if and only if the for each subgraph induced by vertices labeled ≤ j (for any j), each connected component contains exactly one vertex achieving the maximum label within that component. This reformulation directly suggests a recursive construction. The maximum-labeled vertex in each component acts as a “separator,” and removing it splits the component into smaller pieces that can be ranked independently with one fewer label level.
No Wolfram Language functions exist specifically for vertex ranking, so our computational challenge is to build a function to perform the following task: given a graph G and an integer k, list every possible k-ranking of G. Our algorithm relies on the following observation: a vertex labelling of a graph is a k-ranking if and only if the for each subgraph induced by vertices labeled ≤ j (for any j), each connected component contains exactly one vertex achieving the maximum label within that component. This reformulation directly suggests a recursive construction. The maximum-labeled vertex in each component acts as a “separator,” and removing it splits the component into smaller pieces that can be ranked independently with one fewer label level.
Implementation
Implementation
We use the definition of a k-ranking as a labeling of vertices with {1,...,k} such that in the subgraph induced by vertices labeled ≤ j (for any j ≤ k), each connected component has exactly one vertex with the maximum label among vertices in that component. We create rankings by assigning labels to certain vertices in stages, at each stage looking at each of the connected components G1,G2,... of the graph created from the original graph G by deleting all of the previously labeled vertices (which means deleting these vertices from the vertex set of G and all edges with at least one of these vertices as an endpoint from the edge set of G) and selecting a vertex u1 from G1, u2 from G2,... so that vertex ui is to be the highest ranked vertex of Gi, then assigning each ui some legal label and stipulating that all other vertices in Gi must be given a label strictly smaller than that label. For instance, if our original graph G has connected graph components G1 and G2, then at the first stage we can let u1 be any vertex in G1, u2 be any vertex in G2, and the label of u1 be any integer between 1 and k and the label of u2 be any integer between 1 and k (since for our purposes a k-ranking just has to be a ranking using just the labels {1,2,...,k} but doesn’t have to actually use every label).
At a given stage each partial ranking will be represented by an Association of the form
<|"Partial Ranking"->ranking_Association,"Component/Rank Pairs"->componentRankPairs_List|>
where the of keys of the Association ranking are the vertices that have been labeled so far in this partial ranking and the value for such a vertex is its label, and each element of the List componentRankPairs is a List whose first element is a connected graph component of the graph created by deleting all of the vertices labeled so far in the partial ranking from the original graph, and whose second element is the largest rank that can be assigned to a vertex in that connected graph component.
For instance, assume our original graph G is connected, and our partial ranking has only labeled one vertex v with the number k, and deleting v from G (which means deleting v from the vertex set of G and all edges with v as an endpoint from the edge set of G) leaves connected graph components G1 and G2, then that partial ranking will be represented by
<|"Partial Ranking"-><|v->k|>,"Component/Rank Pairs"->{{G1,k-1},{G2,k-1}}|>
since we are stipulating that v is the highest ranked vertex in G, so each vertex in G1 and G2 can have rank higher than k-1. Then suppose we select some vertex u1 from G1 to be labeled l1 and some vertex u2 from G2 to be labeled l2 (where 1<=l1<=k-1 and 1<=l2<=k-1), and deleting u1 from G1 leaves connected graph components G11 and G12 while deleting u2 from G2 leaves connected graph components G21, G22, and G23. The representation for this extended partial ranking will look like
<|"Partial Ranking"-><|v->k,u1->l1,u2->l2|>,"Component/Rank Pairs"->{{G11,l1-1},{G12,l1-1},{G21,l2-1},{G22,l2-1},{G23,l2-1}}|>
Note that from each partial ranking, we need to create a list of all possible extensions of that partial ranking. In the previous example, that means considering each Tuple {u1,u2} where u1 is a vertex of G1 and u2 is a vertex of G2, and each Tuple {l1,l2} where l1 is a label between 1 and k-1 for u1 and l2 is a label between 1 and k-1 for u2.
Our outer function will look like the following, starting with a singleton List whose only element is the Association representing the empty partial ranking, and calling function extendRanking, which will take as input the Association partialRankingInfoAssoc of the form <|”Partial Ranking”->ranking_Association,”Component/Rank Pairs”->componentRankPairs_List|> described above, and will output a List of Associations of the same form, representing each possible extension of the given partial ranking in the manner described above:
FindAllRankings[graph_Graph,(k_Integer)?Positive]:=Module[{partialRankingInfoAssocList},partialRankingInfoAssocList=FixedPoint[Flatten@*Map[extendRanking],{<|"Partial Ranking"-><||>,"Component/Rank Pairs"->({#,k}&/@ConnectedGraphComponents[graph])|>}];Through[(Map/@Through[partialRankingInfoAssocList["Partial Ranking"]])[VertexList[graph]]]]
Note that if the second element of any of the pairs in componentRankPairs is 0, then extendRanking should return {}, since that means no available labels are left to use on any vertex in some connected graph component. In the general case, VertexList retrieves the candidate separator vertices for each active component; Tuples forms the Cartesian product of those vertex lists, yielding every combination of separator choices (one per component). For each such vertex combination, we call the function rankComponents to generate all legal label assignments.
extendRanking[partialRankingInfoAssoc_]:=Module[{partialRanking,componentRankPairs,components,maxRanks,vertexChoices,labelChoices,vertexCombinations,allExtensions},(*Extractthepartialrankingandcomponent/rankpairs*)partialRanking=partialRankingInfoAssoc["Partial Ranking"];componentRankPairs=partialRankingInfoAssoc["Component/Rank Pairs"];(*Ifanycomponenthasmaxrank0,returnemptylist*)If[MemberQ[Part[#,2]&/@componentRankPairs,0],Return[{}]];(*Extractcomponentsandtheirmaxranks*)components=Part[#,1]&/@componentRankPairs;maxRanks=Part[#,2]&/@componentRankPairs;(*Foreachcomponent,getlistofvertices*)vertexChoices=VertexList/@components;(*Foreachcomponent,getlistofpossiblelabels(1tomaxRank)*)labelChoices=Range/@maxRanks;(*GenerateallcombinationsofvertexselectionsusingTuples*)vertexCombinations=Tuples[vertexChoices];(*Foreachvertexcombination,generatealllabelcombinationsandcreatenewrankings*)allExtensions=Flatten[Map[rankComponents[labelChoices,partialRanking,components],vertexCombinations],1];allExtensions]
Base case 1: empty component list returns the completed ranking. Base case 2: any component with budget 0 returns {} (prune). General case: Tuples over vertex and label choices, mapped through rankComponents, then flattened one level.
Given a fixed tuple of separator vertices, rankComponents enumerates every legal way to assign labels to them, calling the function assignLabels to produce the resulting states.
In[]:=
rankComponents[labelChoices_,partialRanking_,components_][vertexTuple_]:=Module[{labelCombinations},labelCombinations=Tuples[labelChoices];Map[assignLabels[partialRanking,vertexTuple,components],labelCombinations]]
Builds all label tuples via Tuples[labelChoices], then maps assignLabels over each combination to produce the list of new partial states for this vertex selection.
The function assignLabels threads the new vertex-to-label pairs into the existing partial ranking via AssociationThread and Join, then calls the function createComponentRankPair on every (component, vertex, label) triple simultaneously using MapThread and flattens the nested output one level. The result is a new canonical state association with keys “Partial Ranking” and “Component/Rank Pairs”, exactly the format the algorithm carries forward to the next iteration.
In[]:=
assignLabels[partialRanking_,vertexTuple_,components_][labelTuple_]:=Module[{newRanking,newComponentRankPairs},newRanking=Join[partialRanking,AssociationThread[vertexTuple,labelTuple]];newComponentRankPairs=Flatten[MapThread[createComponentRankPair,{components,vertexTuple,labelTuple}],1];<|"Partial Ranking"->newRanking,"Component/Rank Pairs"->newComponentRankPairs|>]
Threads vertex-label pairs into the partial ranking via AssociationThread and Join, then applies createComponentRankPair across all active components simultaneously using MapThread. Returns the updated state association.
The function createComponentRankPair takes the given component, the chosen separator vertex, and its assigned label j, then deletes that vertex with VertexDelete, calls ConnectedGraphComponents on the remainder, and return each resulting sub-component paired with rank budget j−1. A leaf vertex whose deletion leaves an empty graph returns an empty list of pairs, which is the algorithm’s signal that no further work is needed in that branch.
In[]:=
createComponentRankPair[comp_,vertex_,label_]:=Module[{newComponents},newComponents=ConnectedGraphComponents[VertexDelete[comp,vertex]];{#,label-1}&/@newComponents]
Deletes the chosen separator vertex, calls ConnectedGraphComponents on the remainder, and pairs each resulting sub-component with rank budget label−1. A leaf vertex returns an empty list.
Visualization
Visualization
We naturally desire functionality to display the rankings produced by FindAllRankings; we provide such functionality below.
Label-Based Visualization
Label-Based Visualization
In[]:=
showVertexRanking[g_Graph][ranking_List]:=Graph[g,VertexLabels->Thread[VertexList[g]->ranking],VertexSize->0.3,VertexLabelStyle->Directive[Bold,14]]
Color-Coded Visualization
Color-Coded Visualization
In[]:=
showVertexRankingColored[g_Graph][ranking_List]:=Module[{maxRank,colorFunc,vertexColors},maxRank=Max[ranking];colorFunc=ColorData["Rainbow"];vertexColors=Thread[VertexList[g]->(colorFunc[(#-1)/Max[1,maxRank-1]]&/@ranking)];Graph[g,VertexLabels->Thread[VertexList[g]->ranking],VertexStyle->vertexColors,VertexSize->0.4,VertexLabelStyle->Directive[Bold,14,White]]]
Grid Display
Grid Display
In[]:=
showAllRankings[g_Graph,rankings_List,cols_Integer:4]:=Grid[Partition[showVertexRankingColored[g]/@rankings,cols,cols,1,{}],Frame->All,Spacings->{1,1}]
Examples and Results
Examples and Results
For the following graphs, we produce and visualize all rankings.
Path Graph
Path Graph
In[]:=
pathGraph=PathGraph[Range[5],VertexLabels->"Name"]
Out[]=
In[]:=
pathRankings=FindAllRankings[pathGraph,3]
Out[]=
{{1,3,1,2,1},{2,3,1,2,1},{2,1,3,2,1},{1,2,3,2,1},{2,1,3,1,2},{1,2,3,1,2},{1,2,1,3,1},{1,2,1,3,2}}
In[]:=
Length[pathRankings]
Out[]=
8
In[]:=
showAllRankings[pathGraph,pathRankings,4]
Out[]=
Cycle Graph
Cycle Graph
Complete Graph
Complete Graph
Star Graph S5
Star Graph S5
Binary Tree
Binary Tree
The Ranking Number
The Ranking Number
The ranking number χr(G) is the smallest k for which G admits a valid k-ranking. We compute it by invoking FindAllRankings with increasing k until the result is non-empty. The function RankingNumber below implements this sweep and returns the minimum such k.
We apply RankingNumber to the graphs defined in the previous section:
Verifying Rankings
Verifying Rankings
To confirm correctness of the enumeration, we implement an independent validator. ValidRankingQ checks the ranking condition directly: for every pair of same-labeled vertices, it verifies that every path between them contains a strictly higher label. This brute-force check is separate from the generative algorithm and serves as a sanity test on all produced rankings.
We apply ValidRankingQ to some of the graphs defined two sections ago:
Conclusion
Conclusion
We have created a function FindAllRankings that lists all k-rankings of a graph G. We applied this function to several graphs, and visualized the results. We intend to submit this function to the Wolfram Function Repository, and use it to determine the structure of minimum rankings of entire classes of graphs, such as 3-dimensional grid graphs.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Enumerating vertex rankings of graphs
by Steve Lu
Wolfram Community, STAFF PICKS, June 2, 2026
https://community.wolfram.com/groups/-/m/t/3725564
by Steve Lu
Wolfram Community, STAFF PICKS, June 2, 2026
https://community.wolfram.com/groups/-/m/t/3725564