CODEWITHSUNDEEP
algorithmgraphgraph-coloring
adolzi
adolzi

Reputation: 691

Optimal edge coloring in bipartite graphs

I've faced with following problem: find the optimal edge coloring in a bipartite graph. I know that greedy coloring algorithm can sometimes not return the optimal number of colors. By 'greedy coloring algorithm' I mean: choose first vertex with the highest degree and color its edges on colors 1...degree, then choose the vertex with degree <= to the previous degree and color every of its incident edge on the first available number (the lowest number which is not used by its neighbour), the choose the next vertex etc.

But I've introduced one modification: the edges of first choosen vertex I color in descending order (degree...1), and edges of the next vertices as previously on 1...degree. This modification resulted in examples which I've come up I've got optimal number of colors. But I'm not pretty sure that it's always a rule. Does somebody know if this version of edge coloring algorithm is optimal, or maybe anyone is able to show any counterexample?

Upvotes: 1

Views: 931

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 153152

You can take your counterexample for the "naive" greedy algorithm and turn it into a counterexample for your "sophisticated" greedy algorithm. Simply insert dummy nodes with appropriate degree to "absorb" the backwards colorings. One can always fabricate a new node with degree n in an arbitrary part of the graph: simply insert n fresh nodes in the other part and connect them each by a single edge to the desired new node.

Since all nodes that get colored in descending order are freshly inserted, all the nodes in the original counterexample are colored in ascending order, hence get the same colors as they would have in the original "naive" greedy algorithm. Since the optimal coloring has at least as many colors as the degree of the original graph, and the freshly inserted nodes all have smaller degree than the original graph's maximal degree, the new graph does not need any more colors than the original. Therefore the coloring produced by the "sophisticated" algorithm -- which will still have more colors than necessary for the original graph -- is not optimal for the new graph.

For example, take the graph described in the comment below, which has nodes B,C,D on the left and E,F,G,H on the right. It has these edges:

B connects to E, F, and G
C connects to E, F, and G
D connects to G and H

For the moment, I will assume only the first node you touch gets colored in descending order. (For other nodes, it is not even clear what "descending order" might mean -- descending from what maximum? The degree of the node may not be high enough.)

Therefore, we insert a new node A on the left and three nodes I, J, and K on the right; the connectivity is now

A connects to I, J, and K
B connects to E, F, and G
C connects to E, F, and G
D connects to G and H

The sophisticated greedy algorithm will therefore color AI-3, AJ-2, AK-1, then proceed as the naive greedy algorithm on the remaining nodes.

Upvotes: 1

Related Questions