0
$\begingroup$

Determine the number of colors needed to label $V(K_n)$ such that each color class induces a subgraph with maximum degree at most $k$.

I'm not sure what this problem is even asking. I know that the complete graph of order $n$ has $n$ different color classes since every vertex is adjacent to every other vertex. Also, induced subgraphs of $K_n$ are also complete graphs of equal or smaller order. What is this problem asking me to do? I am lost. Any hints or solutions are greatly appreciated.

$\endgroup$
0
$\begingroup$

HINT:

In this problem you are not asked for a "proper" coloring. This means that it is allowed for adjacent vertices to have the same color.

Now an induced subgraph of a complete graph is itself a complete graph. This means that maximum degree at most $k$ implies that such a subgraph can have at most $k+1$ vertices.

Can you finish it by yourself?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.