On the minimum rainbow subgraph number of a graph

Ingo Schiermeyer


We consider the Minimum Rainbow Subgraph problem (MRS): Given a graph G, whose edges are coloured with p colours. Find a subgraph FG 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.


Edge colouring, rainbow subgraph.

Full Text:


DOI: https://doi.org/10.26493/1855-3974.246.94d

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications