For a graph $G$ and integer $qgeq 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 {em anti-Ramsey} numbers. Algorithmically, the problem is NP-Hard for $qgeq 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,ldots, 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 + frac {2} {delta})$ for graphs with perfect matching and minimum degree $delta$. For $delta ge 4$, this is better than the $frac {5} {3}$ approximation guarantee proved in {AAAP}. For triangle free graphs with perfect matching, we prove that the approximation factor is $(1 + frac {1}{delta - 1})$, which is better than $5/3$ for $delta ge 3$.
Download