Coloring graphs

  • #1
391
0
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
 

Answers and Replies

  • #2
matt grime
Science Advisor
Homework Helper
9,395
4
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.
 

Related Threads on Coloring graphs

  • Last Post
Replies
9
Views
1K
Replies
4
Views
3K
Q
Top