coloring graphs

zetafunction

given a bipartite graph , how do i know that two colors are enough to paint it ??

another question given a general graph , how do i know how many colors do i need to color it

of course in any case there can not be adjacent colors in vertices

matt grime

1) Because it is bipartite - look at the definition of bipartite

2) Computing the chromatic number is NP-complete, so in general you don't know if it can be coloured with k colours by any cheap calculation.