Abstract
The anti-Ramsey number with input graph and pattern graph , is the maximum positive integer such that there exists an edge coloring of using colors, in which there are no rainbow subgraphs isomorphic to in . ( 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 (for ) 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 -coloring problem. For a graph and an integer , an edge -coloring of is an assignment of colors to edges of , such that edges incident on a vertex span at most distinct colors. The maximum edge -coloring problem seeks to maximize the number of colors in an edge -coloring of the graph . Note that the optimum value of the edge -coloring problem of equals . In this paper, we study , the anti-Ramsey number of stars, for each fixed integer , both from combinatorial and algorithmic point of view. The first of our main results presents an upper bound for , in terms of number of vertices and the minimum degree of . The second one improves this result for the case of triangle-free input graphs. For a positive integer , let denote a subgraph of with maximum number of possible edges and maximum degree . Our third main result presents an upper bound for in terms of . All our results have algorithmic consequences.
Connections
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 review
No reviews yet.
Discussion 0
Add a comment
No comments yet.