# Maximising a particular colour in a vertex colouring

I'm looking for a paper that discusses the maximising of one colour in a vertex colouring.

Suppose that for an unweighted, undirected graph $G=(V,E)$ we define a vertex colouring as a function $c : V\to\mathbb N$ (where we use $\mathbb N$ for the colours). I would then like to maximise $\#\{v\in V\mid c(v)=n\}$ for particular $n\in\mathbb N$. The algorithm should return the size of the largest set of vertices that can be coloured with the same colour.

Has there been any literature on this topic?

• Is there any bound on the number of colors you're allowed to use? Otherwise this is just finding a maximum independent set. – Tom van der Zanden Oct 21 '15 at 20:00
• @TomvanderZanden no restriction. I didn't know the term 'independent set'! I saw it's NP-hard, but that there are some 'not-too-exponential' algorithms; en.wikipedia.org/wiki/…. So, many thanks for that! – user23039 Oct 21 '15 at 20:04