Abstract

The anti-Ramsey number ar(G,H)ar(G,H) with input graph GG and pattern graph HH, is the maximum positive integer kk such that there exists an edge coloring of GG using kk colors, in which there are no rainbow subgraphs isomorphic to HH in GG. (HH is rainbow if all its edges get distinct colors). The concept of anti-Ramsey number was introduced by Erdös, Simanovitz, and Sós 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 K1,tK_{1,t} (for t≥3t \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 qq-coloring problem. For a graph GG and an integer q≥2q\geq 2, an edge qq-coloring of GG is an assignment of colors to edges of GG, such that edges incident on a vertex span at most qq distinct colors. The maximum edge qq-coloring problem seeks to maximize the number of colors in an edge qq-coloring of the graph GG. Note that the optimum value of the edge qq-coloring problem of GG equals ar(G,K1,q+1)ar(G,K_{1,q+1}). In this paper, we study ar(G,K1,t)ar(G,K_{1,t}), the anti-Ramsey number of stars, for each fixed integer t≥3t\geq 3, both from combinatorial and algorithmic point of view. The first of our main results presents an upper bound for ar(G,K1,q+1)ar(G,K_{1,q+1}), in terms of number of vertices and the minimum degree of GG. The second one improves this result for the case of triangle-free input graphs. For a positive integer tt, let HtH_t denote a subgraph of GG with maximum number of possible edges and maximum degree tt. Our third main result presents an upper bound for ar(G,K1,q+1)ar(G,K_{1,q+1}) in terms of ∣E(Hq−1)∣|E(H_{q-1})|. All our results have algorithmic consequences.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.