Search

Given a graph G, the anti-Ramsey number $$AR(K_n,G)$$ is defined to be the maximum number of colors in an edge-coloring of $$K_n$$ which does not contain any rainbow G (i.e., all the edges of G have distinct colors). The anti-Ramsey number was introduced by Erdős et al. (Infinite and finite sets, pp 657–665, 1973) and so far it has been determined for several special graph classes. Another related interesting problem posed by Erdős et al. is the uniqueness of the extremal coloring for the anti-Ramsey number. Contrary to the anti-Ramsey number, there are few results about the extremal coloring. In this paper, we show the uniqueness of such extremal coloring for the anti-Ramsey number of matchings in the complete graph.

The heterochromatic tree partition number of an $$r$$ -edge-colored graph $$G,$$ denoted by $$t_r(G),$$ is the minimum positive integer $$p$$ such that whenever the edges of the graph $$G$$ are colored with $$r$$ colors, the vertices of $$G$$ can be covered by at most $$p$$ vertex disjoint heterochromatic trees. In this article we determine the upper and lower bounds for the heterochromatic tree partition number $$t_r(K_{n_1,n_2,\ldots ,n_k})$$ of an $$r$$ -edge-colored complete $$k$$ -partite graph $$K_{n_1,n_2,\ldots ,n_k}$$ , and the gap between upper and lower bounds is at most one.

In this paper we consider the problem of partitioning complete multipartite graphs with edges colored by 2 colors into the minimum number of vertex disjoint monochromatic cycles, paths and trees, respectively. For general graphs we simply address the decision version of these three problems the 2-PGMC, 2-PGMP and 2-PGMT problems, respectively. We show that both 2-PGMC and 2-PGMP problems are NP-complete for complete multipartite graphs and the 2-PGMT problem is NP-complete for bipartite graphs. This also implies that all these three problems are NP-complete for general graphs, which solves a question proposed by the authors in a previous paper. Nevertheless, we show that the 2-PGMT problem can be solved in polynomial time for complete multipartite graphs.