How is edge coloring satisfied in this code?

asked 2023-04-21 12:36:58 +0200

vidyarthi gravatar image

I saw the beautiful code written on this site of using Mixed Integer Linear Programming for total coloring here.

In it two mip variables are defined corresponding to edges and vertices and constraints are so created that it satisfies the conditions of total coloring, except that I notice that we only ensure that the sum of binary variables of adjacent vertices is less than or equal to $1$ , and also that the sum of binary variables corresponding to adjacent vertices and their incident edges is also less than or equal to $1$. Now, how does this ensure that the adjacent edges, or those edges incident on any single vertex receive different colors, like we are not writing b[(v,w),c]+b[(v,u),c]<=1 right, where v,w,u are vertices (v is adjacent to w and u). How is that condition met? Any clarifications? Thanks beforehand.

edit retag flag offensive close merge delete



Read again constraint p.add_constraint(bv[v,c] + sum(be[e,c] for e in G.edges_incident(v, labels=False)) <= 1). It ensures that color c can be assigned to at most one among vertex v and the edges incident to v. Consequently, edges incident to v are assigned different colors.

David Coudert gravatar imageDavid Coudert ( 2023-04-22 12:12:54 +0200 )edit