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.

Locations

• Ars Mathematica Contemporanea - View - PDF