Please provide your feedback about the website at feedback@apc.iisc.ernet.in
The anti-Ramsey number, ar(G, H) is the minimum integer k such that in any edge colouring of G with k colours there is a rainbow subgraph isomorphic to H, namely, a copy of H with each of its edges assigned a different colour. The notion was introduced by Erd{\”{o}}s and Simonovits in 1973. The case when H is a star graph was considered by several graph theorists from the combinatorial point of view. Recently this case received the attention of researchers from the algorithm community because of its applications in interface modelling of wireless networks. To the algorithm community, the problem is known as maximum edge q-colouring problem: Find a coloring of the edges of G, maximizing the number of colors satisfying the constraint that each vertex spans at most q colors on its incident edges.
Recently we studied the maximum edge 2-coloring problem from the approximation algorithm point of view. The case q=2 is particularly interesting from the application point of view. Algorithmically, this problem is known to be NP-hard for $q\ge2$. For the case of $q=2$, it is also known that no polynomial time algorithm can approximate to a factor less than $3/2$ assuming the unique games conjecture. Some of our new results on this problem is published recently in Discrete Applied Mathematics (Available online 5 June 2021). Another paper is in progress. Our work improves approximation factors compared to the previously known approximation algorithms for some non-trivial special cases.
References
L. Sunil Chandran, Abhiruk Lahiri, Nitin Singh, Improved approximation for maximum edge colouring problem, Discrete Applied Mathematics, 2021, ISSN 0166-218X,
