n is the number of vertex and Bruteforce is O(3^n)..Thanks in advance.
(it's a additional exercise of SRM487D1_550pt)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
UPD: Never mind, seems I played an idiot again. ;-)
I am sorry for what I am saying (since I may be wrong), but it looks that 2^n or 3^n are too much for coloring of the graph (or may be I misunderstood your problem?)
I suppose that proper page of wikipedia could give few hints on the topic. The problem seems to be of DP type and I guess it could be done in polynomial time.
(Sorry for being not exact - I did not read the article in wikipedia myself still because I want to try to invent solution myself before reading any hints)
Second attempt:
Is it correct, that if graph is not 3-colorable, it necessarily have such 4 vertexes, that have all 6 edges between them?
If true, than we could check C(n,4) combinations of vertexes of the graph and for all of them check this property. It would give O(n^4) but I think I am missing something important.