Ask Your Question

fractional chromatic index of edge-weighted graphs

asked 2019-06-11 10:52:15 +0200

anonymous user


updated 2019-06-11 11:03:51 +0200

How would you compute the fractional chromatic index of an edge-weighted graph using SAGE?

The built-in function fractional_chromatic_index seems to compute the fractional chromatic index for only unweighted graphs. For instance, if $G$ is the 5-cycle graph, its fractional chromatic index is $2.5$. But if one of the edges can be ignored, say by giving it a zero weight, then the fractional chromatic index becomes $2$.

The code and output below shows that SAGE ignores the edge-weights (notice that the edge-weights need not be integral - in the graph below, the correct value of the fractional chromatic index is 2.1, which is the maximum sum $1.1+1.0$ of weights of edges incident to a vertex):

sage: G = graphs.EmptyGraph()
sage: G.add_edges([(1,2,1.1),(2,3,1),(3,4,1),(4,5,1),(5,1,0)])
sage: G.fractional_chromatic_index()

Is there some way to get the built-in function to take edge weights into account? Or can this value be computed using some other method?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2019-06-11 22:05:12 +0200

tmonteil gravatar image

updated 2019-06-11 22:05:34 +0200

The fractional chromatic index is computed via linear programming and duality. Its Sage implementation is pretty clear and documented line-by-line, you can read and adapt it to the weighted case by typing:

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2019-06-11 10:52:15 +0200

Seen: 161 times

Last updated: Jun 11 '19