# Complexity of two promise graph coloring problems [closed]

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?
• 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'$. – Yonatan N May 20 at 8:24
• ' each color used exactly n+1 times' why? – T.... May 20 at 10:20
• 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. – Yonatan N May 20 at 17:08
• @YonatanN So this answers II.3. – T.... May 21 at 6:59
• 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. – Yonatan N May 21 at 7:10