Timeline for A decision problem in graph coloring
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 9, 2010 at 14:35 | comment | added | Joseph O'Rourke | @Muse & domotorp: Thanks for the clarifications! | |
| Jul 9, 2010 at 14:07 | comment | added | Muse | The coloring problem equivalent to partitioning the graph into cliques of size at least 2. This problem is quoted as polynomial-tim solvable in portal.acm.org/citation.cfm?id=1518279 . I refer to the 2nd paragraph in the introduction where it is stated that checking whether a graph can be packed by K_2, K_3,....K_n can be checked efficiently. 'Hell and Kirkpatrick [3] showed that this problem is NP-hard when F contains only complete graphs with at least three vertices, and it is polynomially solvable when F = {K2, . . . , Kr}, r > 2. | |
| Jul 9, 2010 at 13:39 | comment | added | domotorp | see my answer for the connection | |
| Jul 9, 2010 at 10:11 | comment | added | Joseph O'Rourke | @unknown: The paper is "Approximation algorithms and hardness results for the clique packing problem." Could you explain how the results in the paper address the posed question? The paper contains many results, and they are not phrased in the same terms as the posed problem. | |
| Jul 9, 2010 at 10:03 | history | answered | Muse | CC BY-SA 2.5 |