Timeline for A decision problem in graph coloring
Current License: CC BY-SA 2.5
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 |