Approximation bounds on maximum edge 2-coloring of dense graphs
share
For a graph G and integer q≥ 2, an edge q-coloring of G is an assignment of colors to edges of G, such that edges incident on a vertex span at most q distinct colors. The maximum edge q-coloring problem seeks to maximize the number of colors in an edge q-coloring of a graph G. The problem has been studied in combinatorics in the context of anti-Ramsey numbers. Algorithmically, the problem is NP-Hard for q≥ 2 and assuming the unique games conjecture, it cannot be approximated in polynomial time to a factor less than 1+1/q. The case q=2, is particularly relevant in practice, and has been well studied from the view point of approximation algorithms. A 2-factor algorithm is known for general graphs, and recently a 5/3-factor approximation bound was shown for graphs with perfect matching. The algorithm (which we refer to as the matching based algorithm) is as follows: "Find a maximum matching M of G. Give distinct colors to the edges of M. Let C_1,C_2,..., C_t be the connected components that results when M is removed from G. To all edges of C_i give the (|M|+i)th color." In this paper, we first show that the approximation guarantee of the matching based algorithm is (1 + 2/δ) for graphs with perfect matching and minimum degree δ. For δ> 4, this is better than the 5/3 approximation guarantee proved in AAAP. For triangle free graphs with perfect matching, we prove that the approximation factor is (1 + 1/δ - 1), which is better than 5/3 for δ> 3.
READ FULL TEXT