| dc.description.abstract | 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 Erdos, Simanovitz, and Sos in 1973. Thereafter several researchers investigated this concept
in the
combinatorial setting. The cases where pattern graph H is a complete graph K_r, a path P_r or a
star K_{1,r} for a fixed positive integer r, are well studied.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}).
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. From an observation of Erdos, Simanovitz, and Sos, we get: |E(H_{q-1})|
+ 1 leq ar(G,K_{1,q+1}) leq |E(H_{q})|. For instance, when q=2, the subgraph E(H_{q-1}) refers to a
maximum matching.
It looks like |E(H_{q-1})| is the most natural parameter associated with the anti-ramsey number
ar(G,K_{1,q+1}) and the approximation algorithms for the maximum edge coloring problem
proceed usually by first computing the H_{q-1}, then
coloring all its edges with different colors and by giving one (sometimes more than one) extra
colors to the remaining edges. The approximation guarantees of these algorithms usually
depend on upper bounds for ar(G,K_{1,q+1}) in terms of |E(H_{q-1})|.
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. For some large special classes of graphs, such
as d-regular graphs, where d geq 4, our results can be used to prove a better approximation
guarantee for the sub-factor based algorithm. We also show that all our bounds are almost tight.
Results for the case q=2 were done earlier by Chandran et al. In this thesis, we extend it further
for each fixed integer q greater then 2 | en_US |
