ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 11 Jun 2019 22:05:12 +0200fractional chromatic index of edge-weighted graphshttps://ask.sagemath.org/question/46900/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.add_edges([(1,2,1.1),(2,3,1),(3,4,1),(4,5,1),(5,1,0)])
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?Tue, 11 Jun 2019 10:52:15 +0200https://ask.sagemath.org/question/46900/fractional-chromatic-index-of-edge-weighted-graphs/Answer by tmonteil for <p>How would you compute the fractional chromatic index of an edge-weighted graph using SAGE? </p>
<p>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$. </p>
<p>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):</p>
<pre><code>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()
5/2
sage:
</code></pre>
<p>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?</p>
https://ask.sagemath.org/question/46900/fractional-chromatic-index-of-edge-weighted-graphs/?answer=46902#post-id-46902The 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??Tue, 11 Jun 2019 22:05:12 +0200https://ask.sagemath.org/question/46900/fractional-chromatic-index-of-edge-weighted-graphs/?answer=46902#post-id-46902