Y by ImSh95
Hi,
I can't get my head about complexity of graph coloring and wiki didn't really help me.
Here is what I think I know:
Generally, Coloring graph is NP-hard problem.
Coloring graph with 3 colors is NP-complete problem.
But I don't get how can it be harder to color a graph when you have more colors. Lets go to extreme, if I had a complete graph with 50 vertices and I had 5000 colors, I don't think it would be really hard to color this graph so graph-coloring properties are met (each vertex new color)... So how can the complexity arise when you have more colors.
I expect that problem/hardness of it is actually in coloring with specific K or maybe deciding what is the smallest K that graph can be colored... But I am not sure, and that is why I am asking for help and clarity.
I can't get my head about complexity of graph coloring and wiki didn't really help me.
Here is what I think I know:
Generally, Coloring graph is NP-hard problem.
Coloring graph with 3 colors is NP-complete problem.
But I don't get how can it be harder to color a graph when you have more colors. Lets go to extreme, if I had a complete graph with 50 vertices and I had 5000 colors, I don't think it would be really hard to color this graph so graph-coloring properties are met (each vertex new color)... So how can the complexity arise when you have more colors.
I expect that problem/hardness of it is actually in coloring with specific K or maybe deciding what is the smallest K that graph can be colored... But I am not sure, and that is why I am asking for help and clarity.