# fractional chromatic index of edge-weighted graphs Anonymous

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.fractional_chromatic_index()
5/2
sage:


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 close merge delete

Sort by » oldest newest most voted

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:

G.fractional_chromatic_index??

more