Processing math: 100%

First time here? Check out the FAQ!

Ask Your Question
0

fractional chromatic index of edge-weighted graphs

asked 5 years ago

anonymous user

Anonymous

updated 5 years ago

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?

Preview: (hide)

1 Answer

Sort by » oldest newest most voted
0

answered 5 years ago

tmonteil gravatar image

updated 5 years ago

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??
Preview: (hide)
link

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

Stats

Asked: 5 years ago

Seen: 247 times

Last updated: Jun 11 '19