Find the Chromatic Number
Python 2.7 - 122 109 111 109 108 103

f=lambda n,e,m=1:any(all(t*m//m**a%m!=t*m//m**b%m for(a,b)in e)for t in range(m**n))and m or f(n,e,m+1)


Usage: 

print f(5, [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)])


Brute force by increasing the chromatic number (m) and check all possible colorings. One coloring can be described as a number in base m. So the possible colorings are 0, 1, ..., m^n-1.

edit: The complete graph of 8 vertices takes quite long. But my laptop solves it in about 10 minutes. The other test cases take only a few seconds. 



edit 2: Read that preprocessing is allowed, so I let the index of the vertices start with 0: shortens t*m//m**x%m to t//m**a%m (-2). Dissolve lambda and put m into function params (-11)



edit 3: preprocessing is not allowed -> back to t*m (+4), simplified // to / (-2).



edit 4: remove square brackets in any (-2), thanks xnor.



edit 5: instead of taking modulo m twice, simply subtract them and afterwards use modulo (-1). This is also quite a performance improvement. All testcases together take about 25 seconds on my laptop. 



edit 6: recursive call instead of while 1: and m+=1 (-5). Thanks again, xnor.