Color edges distinctly in network based on attribute value

Question

Consider an undirected multigraph (without self-loops) in which the maximum vertex degree d=8 (in other words, there are at most 4 edges between two neighboring nodes).

I would like to assign to each of the parallel edges between two neighboring nodes a unique number from the set {1,2,3,4} based on the edges' attribute values z, given that:

• the attribute value z of each of the parallel edges between two nodes is guaranteed to be unique;
• the attribute values can however be repeated in neighboring edges;
• an attribute value from a parallel edge is only repeated in neighboring edges (cluster), but it never re-occurs elsewhere in the network (only 1 single cluster per attribute value);
• in principle I consider this to be an undirected network, but I can also make it directed if so required.

I am not sure this can be solved with only 4 colors/numbers. The above may be relaxed to a larger set of numbers if required.

I am looking for an algorithm that can solve this problem using the Python package networkx.

Below I give some examples of sections of the network that can occur. In these examples, the | indicates a node, and the z values the edges with attribute value z_{i}

z1 | z1,z2 | z2 | z2,z3 | z3 | z3 | z3,z4 | z4

z1 | z1,z2 | z1,z2,z3 | z2,z3 | z3

z1 | z1,z2 | z1,z2,z3 | z1,z2,z3,z4 | z1,z2,z3,z4 | z2,z3,z4 | z3,z4 | z4

Although it is trivial to color the sections as shown in the examples, the point is that there are branches in the network that converge at which the numbering should be unique again.

I have seen that networkx does have a function to uniquely color nodes. There also exist edge coloring algorithms, but this problem is different in the sense that I do not want each edge to have a unique color.

My feeling is that this requires a greedy algorithm as I read it is in general an NP-hard problem, but due to some of the conditions above I imagine smarter algorithms exist?