-2
$\begingroup$

I. Consider the problem 'Given a chromatic number $k$ graph on $n$ vertices then for all coloring with $k$ colors is there always a color with at least $m$ vertices?'.

  1. What is the known complexity class of this problem?

  2. Is it $NP$ complete when $k=3$ or $k$ is fixed?

II. Consider the problem 'Given a chromatic number $k$ graph on $n$ vertices is there a coloring with same color in at least $m$ vertices?'.

This is in $NP$ complexity class.

  1. Is it $NP$ complete when $k=3$ or $k$ is fixed?
$\endgroup$
  • 1
    $\begingroup$ Let $T_{m,n}$ be the variant of $K_{m,n}$ where edges are added into the "$m$" component to make it complete. Given a 4-colorable graph $G$ on $n$ vertices, construct $G'$ by taking the disjoint union of $T_{3,n+1}$ and 3 copies of $G$. If $G$ is 3-colorable, then $G'$ is $4$-colorable with each color used exactly $n+1$ times. If $G$ is not 3-colorable, then at least one color is used $n+2$ times in all proper $4$-colorings of $G'$. $\endgroup$ – Yonatan N May 20 at 8:24
  • $\begingroup$ ' each color used exactly n+1 times' why? $\endgroup$ – T.... May 20 at 10:20
  • $\begingroup$ If $G$ is 3-colorable, the 3 copies of $G$ can be colored with each color used exactly $n$ times by permuting the roles of the colors. That is, if $\varphi : V\rightarrow [3]$ is 3-coloring function of $G$, so are $d \cdot \varphi$ and $d^{-1}\cdot \varphi$ where $d : [3]\rightarrow [3]$ is a derangement of $[3]$. So we color the three copies of $G$ using $\varphi$, $(d \cdot \varphi)$, and $(d^{-1} \cdot \varphi)$, ensuring each of the colors is used exactly $n$ times. The $T_{3,n+1}$ subgraph can be colored using each of these colors one additional time, plus the remaining color $n+1$ times. $\endgroup$ – Yonatan N May 20 at 17:08
  • $\begingroup$ @YonatanN So this answers II.3. $\endgroup$ – T.... May 21 at 6:59
  • $\begingroup$ I think it answers I.2 by showing that it is co-NP-Hard (so NP-Complete under Cook reductions, but not under Karp unless NP=co-NP). As a corollary, the problem is co-NP-Complete, probably answering I.1. $\endgroup$ – Yonatan N May 21 at 7:10