Originators: Chandra Chekuri (presented by Ch. Sobhan babu - REGS 2010)
Definitions: A multigraph may have multiple edges with the same two endpoints. A proper edge-coloring assigns of colors to the edges so that no two incident edges have the same color. The maximum vertex degree Δ(G) is the largest number of edges at any vertex, counted with multiplicity.
Background: Shannon proved that ⌊3⁄2 Δ(G)⌋ colors suffice for proper edge-coloring of any multigraph G. 3-vertex multigraphs in which each vertex pair appears with the same multiplicity show that the bound is sharp.
Chekuri introduced a path-coloring problem on trees that generalizes the edge-coloring problem on multigraphs. We are given a tree T with positive integer capacities on the edges. We are also given an integer k and a multiset S of paths in T such that for each edge e in T, the number of paths in S that use e is at most k times the capacity of e.
For each such instance, we ask how many colors we need to color the elements of S such that for any edge e in T and any color c, the number of elements in S having color c that use the edge e is at most the capacity of e.
Question: As a function of k, what is the maximum number of colors that may be needed?
Comments: To model edge-coloring as a special case of this problem, let T be a star whose leaves correspond to the vertices of G, let each edge have capacity 1, let k=Δ(G), and let S consist of paths of length 2 corresponding to the edges of G. Since each vertex of G has degree at most k, at most k paths in S use each edge of T. When we color the paths, only one corresponding to an edge incident to a given vertex can receive a given color.
The extremal example for Shannon's Theorem shows that 3k/2 colors may be needed. Chekuri, Mydlarz, and Shepherd [CMS] introced the path-coloring problem as a generalization of proper edge-coloring of multigraphs and presented an algorithm that always uses at most 4k colors. Hence the answer is between 3k/2 and 4k.
References:
[CMS] Chandra Chekuri, Marcelo Mydlarz and F. Bruce Shepherd,
Multicommodity Demand Flow in a Tree and Packing Integer Programs,
ACM Transactions on Algorithms (TALG), 3(3), 2007.