This tracks the rustworkx part of https://github.com/Qiskit/qiskit/issues/11779#issue-2130965930. The request is to add other standard greedy node coloring strategies, such as the "saturation first" strategy: always picking the node that has the largest number of different colors assigned to its neighbors, and, in case of a tie, the node that has the largest number of uncolored neighbors.
What is the expected enhancement?
This tracks the rustworkx part of https://github.com/Qiskit/qiskit/issues/11779#issue-2130965930. The request is to add other standard greedy node coloring strategies, such as the "saturation first" strategy: always picking the node that has the largest number of different colors assigned to its neighbors, and, in case of a tie, the node that has the largest number of uncolored neighbors.
This will be immediately followed up by a PR.