Coloring graphs

  • #1
zetafunction
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,420
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.
 

Suggested for: Coloring graphs

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