On the minimum rainbow subgraph number of a graph

Abstract

We consider the Minimum Rainbow Subgraph problem (MRS): Given a graph G, whose edges are coloured with p colours. Find a subgraph F ⊆ G of minimum order and with p edges such that each colour occurs exactly once. This problem is NP-hard and APX-hard. For a given graph G and an edge colouring c with p colours we define the rainbow subgraph number rs(G, c) to be the order of a minimum rainbow subgraph of G with size p. In this paper we will show lower and upper bounds for the rainbow subgraph number of a graph.