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?

  • 1
    $\begingroup$ Is there any bound on the number of colors you're allowed to use? Otherwise this is just finding a maximum independent set. $\endgroup$ – Tom van der Zanden Oct 21 '15 at 20:00
  • $\begingroup$ @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! $\endgroup$ – user23039 Oct 21 '15 at 20:04

Your problem is just the (maximum) independent set problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy