  The anti-Ramsey number $ar(G,H)$ with input graph $G$ and pattern graph $H$,
is the maximum positive integer $k$ such that there exists an edge coloring of
$G$ using $k$ colors, in which there are no rainbow subgraphs isomorphic to $H$
in $G$. ($H$ is rainbow if all its edges get distinct colors). The concept of
anti-Ramsey number was introduced by Erd\"os, Simanovitz, and S\'os in 1973.
Thereafter several researchers investigated this concept in the combinatorial
setting. Recently, Feng et al. revisited the anti-Ramsey problem for the
pattern graph $K_{1,t}$ (for $t \geq 3$) purely from an algorithmic point of
view due to its applications in interference modeling of wireless networks.
They posed it as an optimization problem, the maximum edge $q$-coloring
problem. For a graph $G$ and an integer $q\geq 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 the graph
$G$. Note that the optimum value of the edge $q$-coloring problem of $G$ equals
$ar(G,K_{1,q+1})$. In this paper, we study $ar(G,K_{1,t})$, the anti-Ramsey
number of stars, for each fixed integer $t\geq 3$, both from combinatorial and
algorithmic point of view. The first of our main results presents an upper
bound for $ar(G,K_{1,q+1})$, in terms of number of vertices and the minimum
degree of $G$. The second one improves this result for the case of
triangle-free input graphs. For a positive integer $t$, let $H_t$ denote a
subgraph of $G$ with maximum number of possible edges and maximum degree $t$.
Our third main result presents an upper bound for $ar(G,K_{1,q+1})$ in terms of
$|E(H_{q-1})|$. All our results have algorithmic consequences.
