Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

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 following code and output shows that SAGE ignores the edge-weights and computes only for unweighted graphs:

sage: G = graphs.EmptyGraph()
sage: G.add_edges([(1,2,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?

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 following code and output below shows that SAGE ignores the edge-weights and computes only for unweighted graphs:(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),(2,3,1),(3,4,1),(4,5,1),(5,1,0)])
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 compute some other way?

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 compute can this value be computed using some other way?method?