duckladydinh's blog

Help on k-coloring of a graph?
By duckladydinh, history, 5 years ago, In English

Hallo,

I am stuck on the following graph problem: How many k-colorings (exactly k, k is a constant) of a sparse graph of n vertexes (n <= 50000) with no connected component of size s having more than s + 2 edges (almost tree).

I am completely stuck!!!

Could someone give me a hint? It's a problem from Hong Kong Regional Online Preliminary 2016 (all of their problems are super hard).

Thanks.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Anyone solve this yet? I'm also stuck and need help.

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I am also trying to solve this. I didn't get anwer till now. But if someone finds the solution please post here. And thanks for sharing problem. It seems good one.

→ Reply