Questions Related to Anti-Ramsey Numbers [L. Sunil Chandran, CSA]

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.



L. Sunil Chandran, Abhiruk Lahiri, Nitin Singh, Improved approximation for maximum edge colouring problem, Discrete Applied Mathematics, 2021, ISSN 0166-218X,

Click image to view enlarged version
Scroll Up