Timeline for A decision problem in graph coloring
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 8, 2010 at 15:55 | comment | added | JBL | No, it's false: consider a star plus an isolated vertex. There are two distinct minimal colorings; in one of them, the center vertex of the star is the only vertex of its color. | |
| Jul 8, 2010 at 14:23 | comment | added | Muse | It is not obvious...maybe it is true...not sure. | |
| Jul 8, 2010 at 14:13 | comment | added | rgrig | Is it true that "if there is a good coloring then any minimum coloring is good"? (where 'good coloring' = 'proper vertex coloring with no solitary color' as required in the question) | |
| Jul 8, 2010 at 10:12 | comment | added | Muse | Yes, we don't need to use the minimum number of colors. So it does not follow from the first response that the problem is NP-hard | |
| Jul 8, 2010 at 9:53 | comment | added | rgrig | But there's no requirement for minimality here. | |
| Jul 8, 2010 at 9:39 | history | answered | Falk Hüffner | CC BY-SA 2.5 |