Happy Thanksgiving! Please note that there are no classes November 25th-December 1st.

MIT PRIMES/Art of Problem Solving

CROWDMATH 2019: Graph Coloring

G
Topic
First Poster
Last Poster
Complexity of graph coloring
GlanePito   0
May 18, 2021
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.
0 replies
GlanePito
May 18, 2021
0 replies
No more topics!
a