# fractional chromatic index of edge-weighted graphs

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