Skip to main content
13 events
when toggle format what by license comment
Jul 9, 2010 at 23:43 answer added Lucas K. timeline score: 0
Jul 9, 2010 at 17:20 answer added Ryan Williams timeline score: 3
Jul 9, 2010 at 10:03 answer added Muse timeline score: 3
Jul 8, 2010 at 20:42 answer added domotorp timeline score: 8
Jul 8, 2010 at 13:45 answer added Jukka Suomela timeline score: 2
Jul 8, 2010 at 12:23 history edited Muse CC BY-SA 2.5
added 26 characters in body
Jul 8, 2010 at 11:42 comment added Niel de Beaudrap Ah, sorry. Somehow I thought the question was how difficult it is to construct one (which obviously would help to answer your question).
Jul 8, 2010 at 10:15 history edited Charles Matthews CC BY-SA 2.5
downcase
Jul 8, 2010 at 9:39 answer added Falk Hüffner timeline score: -1
Jul 8, 2010 at 9:25 comment added Muse Yes, I know, there may not be a proper vertex coloring (where each color is used at least twice) for a given graph. The question is that what is the complexity of checking this?
Jul 8, 2010 at 9:23 history edited Muse CC BY-SA 2.5
added 7 characters in body
Jul 8, 2010 at 9:08 comment added Niel de Beaudrap You will have to be more specific. It is not always possible to have a proper (vertex?) colouring of a graph of this sort: for instance, consider the 3-colouring of the 5-cycle.
Jul 8, 2010 at 7:36 history asked Muse CC BY-SA 2.5