Coloring graphs

  • #1
391
0

Main Question or Discussion Point

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
3
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 for: Coloring graphs

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