Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Coloring graphs

  1. May 4, 2009 #1
    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
  2. jcsd
  3. May 4, 2009 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Coloring graphs
  1. Question on Graph (Replies: 1)

  2. Groups and graphs (Replies: 1)

  3. Graph theory (Replies: 1)

  4. Graphing a plane (Replies: 2)