Timeline for A decision problem in graph coloring
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S May 14, 2023 at 15:19 | history | suggested | The Amplitwist | CC BY-SA 4.0 |
fixed broken links to sciencedirect.com; added full citations using the citation helper; added links to Muse and Ryan Williams's answers
|
| May 14, 2023 at 11:54 | review | Suggested edits | |||
| S May 14, 2023 at 15:19 | |||||
| Jul 12, 2010 at 19:51 | comment | added | domotorp | I think that the 5-cycle is just a graph for which the answer is NO. As it contains no matching*, it does not have a coloring which each colorclass having size at least two. | |
| Jul 12, 2010 at 13:01 | comment | added | Niel de Beaudrap | A 5-cycle is it's own complement, and contains neither a perfect-matching, nor a perfect-matching-asterisk. Thus, the 5-cycle is a graph for which your reduction does not work. | |
| Jul 9, 2010 at 17:44 | history | edited | domotorp | CC BY-SA 2.5 |
added 378 characters in body; added 54 characters in body
|
| Jul 9, 2010 at 13:44 | history | edited | domotorp | CC BY-SA 2.5 |
added 456 characters in body; deleted 147 characters in body; added 39 characters in body
|
| Jul 9, 2010 at 13:37 | comment | added | domotorp | That is why I wrote matching* and not matching - I said that we also allow K_3's to be matched together. It is unnecessary to allow bigger cliques. I don't get what you are trying to say with the 5-cycle. | |
| Jul 9, 2010 at 13:08 | comment | added | Niel de Beaudrap | If the graph has a perfect matching, then this suffices to yield a solution; but the original problem is not equivalent to whether the complement has a perfect matching. Again, consider the 5-cycle. --- More generally, it suffices for the complement to be covered by a vertex-disjoint collection of cliques, where each clique has size at least 2; a perfect matching is a special case. | |
| Jul 8, 2010 at 22:28 | comment | added | Rune | +1 for the statement "it is not hard to show that it is in P. Or NP-complete..." | |
| Jul 8, 2010 at 20:42 | history | answered | domotorp | CC BY-SA 2.5 |