The answer is $\lceil \frac{n}{4k}\rceil$. The construction is as follows: let $n=4kq+r$ where $1\le r\le 4k$. Then the graph $$\underbrace{K_{4k} \sqcup \cdots \sqcup K_{4k}}_q \sqcup K_r$$ works (gives answer of $q+1=\lceil \frac{n}{4k}\rceil$) The general idea is to bound the number of edges, then use Caro-Wei theorem to finish. Some notations: $G[X]$ denoted the induced subgraph of $X$. i.e. a graph $(X,E')$ with vertices in $X$, and two vertices are connected by an edge in $G[X]$ if and only if they are connected by an edge in $G$. $e(A,B)$ is the number of edges with one vertex in $A$ and the other vertex in $B$. We sometimes denote this $c(G)$ if $G=A\sqcup B$. $s(G)$ denote the number of vertices on the same side. That is, if $e(A)$ is the number of edges in $G[A]$, then if we partition $G$ into $A\sqcup B$, then $s(G) = e(A) + e(B)$. [Lemma] If there is a connected component with $V$ vertices and $E$ edges, then the maximum number of crossing edges is at least $\frac{E}{2} + \frac{V-1}{4}$. Furthermore, if $V$ is even, then the maximum number of crossing edges is at least $\frac{E}{2} + \frac{V}{4}$. In other words, if $c$ is the number of crossing edges and $s$ is the number of single-sided edges, then $c-s \ge \frac{V-1}{2}$ [Proof of Lemma] We induct on $V$. If $V$ is even, if we can divide the graph into two sets of vertices $X\sqcup Y$ such that $|X|, |Y|$ are even and $X,Y$ are connected, then we are done because we can partition $X$ into $X_1,X_2$ such that $c_x-s_x\ge \frac{|X|}{2}$, and partition $Y$ into $Y_1,Y_2$ such that $c_y-s_y\ge \frac{|Y|}{2}$. Then $(X_1\cup Y_1), (X_2\cup Y_2)$ or $(X_1\cup Y_2),(X_2\cup Y_1)$ works. If I partition $G$ into $X_1\cup Y_1, X_2\cup Y_2$, then $c-s$ is $$\frac{|X|+|Y|}{2} + e(X_1,Y_2) + e(X_2, Y_1) - e(X_1,Y_1) - e(X_2,Y_2)$$ On the other hand, if I partition $G$ into $X_1\cup Y_2, X_2\cup Y_1$, then $c-s$ is $$\frac{|X|+|Y|}{2} + e(X_1,Y_1) + e(X_2, Y_2) - e(X_1,Y_2) - e(X_2,Y_1)$$ So at least one of the two ways of coloring works. Consider a tree where $v$ is adjacent to all neighbours in $G$. Call the neighbours $n_1,\cdots,n_l$. If some $n_j$ subtree in the spanning tree (call $T_j$) has even size, then letting $X$ be the vertices of $T_j$ works. Otherwise, if all $n_j$ subtrees have odd size, then if there is a crossing edge (in $G$) between $n_j, n_m$ then taking $X$ to be $T_j \sqcup T_m$ works. Otherwise, there are no crossing edge between $n_j,n_m$ for all $n_j,n_m$. This implies that $l$ is odd. For each $n_j$ subtree (say with $f_j$ vertices), I can partition it such that $c(n_j)-s(n_j) \ge \frac{f_j-1}{2}$. After doing that I make all neighbours of $v$ in the same group and $v$ in the other group. If $V$ is odd, then (*) works much more easily (taking a vertex or any $T_j$ gives what we want). [Lemma 2: Characterization of "orz" subgraphs that don't let us immediately finish] If $V$ is odd, equality only holds when $G$ is the union of a bunch of (maximal as size cannot be increased) cliques of odd size (call $L_1, L_2, \cdots, L_m$), where two distinct cliques intersect at at most one vertex, and there are no crossing edges between $L_j$ and $L_l$ for any $1\le j<l\le m$. In other words, each edge is in a maximal clique (which always have an odd number of vertices). Furthermore, there does not exist cliques $L_{j_1}, \cdots, L_{j_l}, L_{j_{l+1}} = L_{j_1}$ such that $L_{j_p} L_{j_{p+1}}$ intersect at a vertex, unless the vertex is the same vertex. Proof of Lemma 2 Call a graph orz if equality holds for that graph (it is clear that the condition described here is sufficient, we need to show it is necessary). We call a graph satisfactory if it meets all criteria in lemma 2. We induct on $|V|$ to show that all orz graphs with $|V|$ vertices ($|V|$ odd) are satisfactory. For smaller $|V|$, orz and satisfactory mean the same thing. Note this means if I partition our vertices into $X,Y\ne \emptyset$, where $|X|$ is odd and $G[X], G[Y]$ are connected, then $G[X]$ is orz and there are an even number of crossing edges. This is true because otherwise, by inductive hypothesis, since $X$ is connected and $G[X] $ is not orz, I can partition $X$ into $X_1\sqcup X_2$ such that $c(X)-s(X) \ge \frac{|X|+1}{2}$. By lemma 1, since $Y$ is connected, I can partition $Y$ into $Y_1\sqcup Y_2$ such that $c(Y)-s(Y) \ge \frac{|Y|}{2}$. Then if I partition $G$ into $X_1\cup Y_1, X_2\cup Y_2$, then $c-s$ is $$\frac{|X|+|Y|+1}{2} + e(X_1,Y_2) + e(X_2, Y_1) - e(X_1,Y_1) - e(X_2,Y_2)$$ On the other hand, if I partition $G$ into $X_1\cup Y_2, X_2\cup Y_1$, then $c-s$ is $$\frac{|X|+|Y|+1}{2} + e(X_1,Y_1) + e(X_2, Y_2) - e(X_1,Y_2) - e(X_2,Y_1)$$ Here, recall $e(A,B)$ is the number of edges with one vertex in $A$ and the other vertex in $B$. One of these two is at least $\frac{|X|+|Y|+1}{2}=\frac{|V|+1}{2}$, so equality does not hold. Therefore, when if I partition our vertices into $X,Y\ne \emptyset$, where $|X|$ is odd and $G[X], G[Y]$ are connected, then $G[X]$ is orz, and $e(X,Y)$ is even. Our proof has two steps: (1) a subset of edges give a satisfactory subgraph. (2) Our graph is satisfactory. Step 1Again, construct a BFS tree from $v$, the vertex with maximum degree. Let the subtrees be $T_1,\cdots,T_m$. If $m=2$ then our graph is a cycle and it is easy to check equality can only be achieved for $C_3 \cong K_3$. Otherwise, $m\ge 3$. For all $j$, if $T_j$ has an odd number of vertices, $G[T_j]$ is orz. Otherwise, $G[V\backslash T_j]$ is orz. If $G[V\backslash T_j]$ is orz for any $j$, then say $$G[V\backslash T_j] = L_1 \cup \cdots \cup L_m$$ We pick $Y$ in our partition carefully. We consider a process starting on $L_{x_0}$ where $x_0=1$. If $L_1$ shares a vertex $w$ with $L_{x_1}$ for some $x_1$, then we go to $L_{x_1}$. Then, if $L_{x_1}$ doesn't contain a shared vertex other than $w$, we take $Y = L_{x_1}\backslash \{w\}$. Otherwise, it contains a shared vertex other than $v$ with $L_{x_2}$ for some $x_2$. At $x_j$, if it has a shared vertex with some $L_{x_{j+1}}$ then we go to $L_{x_{j+1}}$. By the definition of orz, I cannot visit the same clique twice (since my first two steps visit two different vertices (in the intersection at least two shared cliques) already. Therefore, this process must end. When it ends, say I am at $L_m$, and it has only one shared vertex, call $w$. Then picking $Y=L_m\backslash \{w\}$ satisfy $G[V\backslash Y]$ is connected. Note $|Y|$ is even, so $|V\backslash Y|$ is odd. This implies $G[V\backslash Y]$ is also orz=satisfactory. Since $G[V\backslash Y]$ is orz, $G$ can be seen as adding a clique $L_m$ to $\{w\}$, so $G$ contains an satisfactory subgraph (with all vertices). To prove the existence of a satisfactory subgraph (with all vertices), it remains to deal with the case where $|T_j|$ is odd for all $j$. This implies that $G[T_j]$ is orz=satisfactory. Case 1: There exists $j<l$, and an edge between a vertex in $T_j$ and another vertex in $T_l$. Then note $T_j\sqcup T_l, V\backslash (T_j\sqcup T_l)$ are both connected. Since $|T_j\sqcup T_l|$ is even, $G[V\backslash (T_j\sqcup T_l)]$ is orz=satisfactory. We proceed like the previous case to show that $G$ contains a subset of edges $E'$ such that $G(V,E')$ is satisfactory. Case 2: For all $j,l$ there doesn't exist a vertex in $T_j$ and another vertex in $T_l$. Since $m\ge 3$ we can show that $G$ is not orz by lemma 1. Step 2: A satisfactory subset of edges on an orz graph implies graph is satisfactorySuppose in our satisfactory subgraph, $L_m$ contains only vertex that is in $L_j$ for some $j\ne m$. Suppose there is an edge between $v_1v_2$ where $v_1\in V\backslash L_m, v_2\in Y$. Case 1: There is exactly one crossing edge of this form. Then I claim our graph isn't actually orz. We first partition $(V\backslash L_m) \cup \{w\}$ into two parts such that $c-s = \frac{|V| - |L_m| + 1 - 1}{2}$. It is possible to partition $L_m$ into two parts (with $w$ already in place, and to be added to our partition of $(V\backslash L_m) \cup \{w\}$) such that $c(L_m)-s(L_m) = \frac{|L_m|-1}{2}$ and $v_2$ is NOT on the same side as $v_1$. This partition proves our graph is not orz. Case 2: There must be at least two crossing edges between $V\backslash L_m$ and $Y$. Say there is another edge $v_3v_4$ where $v_1\in V\backslash L_m, v_2\in Y$. WLOG, $v_3\ne v_1$. If $v_1$ is not in the intersection of two cliques in the orz induced subgraph $G[V\backslash Y]$, then we take $G=X'\sqcup Y', Y' = \{v_1,v_2\}$. Then note $X'$ is connected, so $G[X']$ is orz. In particular, $v_3,v_4$ must be in the same clique. Say $v_3$ is in $L_j$ in $G[(V\backslash L_m)\cup \{v\}]$ and any path from a vertex in $L_j$ to $w$ needs to go through $L_{j_1}, \cdots, L_{j_t}$ to get to $w$ (note this sequence is unique). Then I claim $G[L_j\cup L_{j_1}\cup \cdots \cup L_{j_t} \cup L_m]$ is a clique. This suffices because if I view this as a process of merging cliques, note that all resulting clique sizes are odd, and the number of cliques decrease, so in the end, I get a satisfactory graph. Let $L$ be the clique containing $v_3$ and $v_4$. Then I can go to $v_3v_4$ via $L$ or via this sequence of (maximal) cliques. If these sequences are different, then we have contradicted our assumption that $G[X']$ is orz=satisfactory. It follows that for the cliques in the path to be maximal cliques, they must be $L$. Satisfactory graphs are orzSuppose in our satisfactory subgraph, $L_m$ contains only vertex that is in $L_j$ for some $j\ne m$. Suppose there is an edge between $v_1v_2$ where $v_1\in V\backslash L_m, v_2\in Y$. Case 1: There is exactly one crossing edge of this form. Then I claim our graph isn't actually orz. We first partition $(V\backslash L_m) \cup \{w\}$ into two parts such that $c-s = \frac{|V| - |L_m| + 1 - 1}{2}$. It is possible to partition $L_m$ into two parts (with $w$ already in place, and to be added to our partition of $(V\backslash L_m) \cup \{w\}$) such that $c(L_m)-s(L_m) = \frac{|L_m|-1}{2}$ and $v_2$ is NOT on the same side as $v_1$. This partition proves our graph is not orz. Case 2: There must be at least two crossing edges between $V\backslash L_m$ and $Y$. Say there is another edge $v_3v_4$ where $v_1\in V\backslash L_m, v_2\in Y$. WLOG, $v_3\ne v_1$. If $v_1$ is not in the intersection of two cliques in the orz induced subgraph $G[V\backslash Y]$, then we take $G=X'\sqcup Y', Y' = \{v_1,v_2\}$. Then note $X'$ is connected, so $G[X']$ is orz. In particular, $v_3,v_4$ must be in the same clique. Say $v_3$ is in $L_j$ in $G[(V\backslash L_m)\cup \{v\}]$ and any path from a vertex in $L_j$ to $w$ needs to go through $L_{j_1}, \cdots, L_{j_t}$ to get to $w$ (note this sequence is unique). Then I claim $G[L_j\cup L_{j_1}\cup \cdots \cup L_{j_t} \cup L_m]$ is a clique. This suffices because if I view this as a process of merging cliques, note that all resulting clique sizes are odd, and the number of cliques decrease, so in the end, I get a satisfactory graph. Let $L$ be the clique containing $v_3$ and $v_4$. Then I can go to $v_3v_4$ via $L$ or via this sequence of (maximal) cliques. If these sequences are different, then we have contradicted our assumption that $G[X']$ is orz=satisfactory. It follows that for the cliques in the path to be maximal cliques, they must be $L$. Now we are done edge bounding. We first do some clique smoothing: Clique smoothingWe do a bunch of operations on the graph such that tries to make some orz components no longer orz, and keep cliques of the same size. Let $m$ be the number of orz components. Case 1: $m\ge 2$ and there exists a maximal clique $L_j$ in one component $C_1$ and another maximal clique $M_t$ in the other component $C_2$ such that $|V(L_j)| > |V(M_t)|$ Let $A$ be a maximal anticlique of Since $|V(L_j)|\ge 5$ and at most one vertex in $L_j$ is in the maximum anticlique of $C_1$, I claim we can "merge" two vertices in $C_1$ such that the maximum anticlique remains. Let $x$ be a vertex in $L_j$, and $v_1,v_2 \in L_j\backslash \{x\}$. We consider a new $C'_1$ as follows: $v_1,v_2$ is contracted into a new vertex $v'$ such that $v'$ is adjacent to whatever vertices originally adjacent to $v_1,v_2$. Then if $S$ is the set of vertices in $C_1$ that is originally in at least two maximal cliques (and edges between two vertices in the same maximal clique), then this operation basically contracts $v_1,v_2$ if $v_1,v_2$ are both in the tree and does nothing otherwise. Therefore, using the same argument as the proof where all satisfactory graphs are orz, we can show that this new connected component $C'_1$ can be partitioned into $X,Y$ such that $c(C'_1)-s(C'-1) = \frac{|C'_1|}{2}$. Of course the maximal anticlique remains. We do something similar on $C_2$: we add a vertex to $M_t$ that increases the size of $M_t$ by 1 (i.e. this vertex is only adjacent to all vertices previously in $M_t$). Clearly, this also doesn't decrease the maximal anticlique, but makes the graph no longer orz. We introduce an important theorem: [Caro-Wei's theorem] $\alpha(G) \ge \sum_{v} \frac{1}{d(v)+1}$. By convexity, $\alpha(G) \ge \frac{V(G)^2}{2E(G)+V(G)}$ Sketch of proof: For each vertex, give it a weight of $\frac{1}{d+1}$. Continually remove the vertex with minimal degree; the weight decreases by at most 1 each step. Case 1: m is at least 2After doing this, let $m$ be the number of orz components. If $m\ge 2$, then all clique sizes of orz components are equal to $u$ for some odd integer $u$. Suppose all clique sizes of orz components are equal to $u$. Final LemmaSuppose $H$ is an orz graph where all cliques have size $u$. Then $|H| \le \alpha(G)u$. Through BFS, we can find a maximal clique $L_t$ with only one vertex $w$ in other maximal cliques. We take a vertex from $L_t\setminus \{w\}$, and delete all vertices in $L_t$. We call this the obliteration of $L_t$ We can write the new graph $G' = L'_1 \cup \cdots \cup L'_q$ where $L'_1$ is what happens to $L_1$ after vertices are removed. All non-obliterated components sizes monotonically decrease, and the hypergraph with vertices in at least two maximum cliques and edges as cliques remains acyclic. Therefore, we get rid of at most $u$ vertices each time, so $|H| \le \alpha(G)u$ Say the disjoint copies of $K_{2t+1}$ have total chromatic number $p$. Then by our lemma the induced subgraph of vertices not in these copies has at least $n-p(2t+1)$ vertices. Furthermore, the maximum number of crossing edges for that induced subgraph is $kn - pt(t+1)$, so $2E+V$ (for that subgraph) is at most $4(kn - pt(t+1))$. Since $\frac{v^2}{2e+v}$ is increasing in $v$, we assume there are exactly $n-p(2t-1)$ vertices. We know by Caro-Wei that it is at least $$\frac{(n-p(2t+1))^2}{4(kn - pt(t+1))}$$So we want to show that $$\frac{(n-m(2t+1))^2}{kn - pt(t+1)} \ge \frac nk - 4p$$Since everything is positive, this is equivalent to $$(n-p(2t+1))^2 \ge \left(\frac nk - 4p\right)(kn - pt(t+1))$$Sub $u=2t+1$, then this is same as $$(n-pu)^2 \ge \left(\frac nk - 4p\right)\left(kn - p\frac{u^2-1}{4}\right)$$ $$\iff (n-pu)^2 \ge \left(\frac nk - 4p\right)\left(kn - p\frac{u^2}{4}\right) + \left(\frac nk - 4p\right)\frac p4$$ $$\iff -2npu \ge -4pkn - p\frac{u^2n}{4k} + \left(\frac nk - 4p\right)\frac p4$$ $$\iff \left(\sqrt{4pkn}-u\sqrt{\frac{pn}{4k}}\right)^2 \ge \left(\frac nk - 4p\right)\frac m4$$ Since $u$ is an odd positive integer, this is minimized when $u=4k\pm 1$. In this case, we need to show $$\frac{pn}{4k} \ge \left(\frac nk - 4p\right)\frac p4$$ Which is obvious by expansion. Case 2: m is 0 or 1It remains to deal with the case where there is 0 or 1 orz component. If there are 0 orz components, then $2E+V\le 4kn$ in our original graph $G$, so $\alpha(G) \ge \frac{V^2}{2E+V} = \frac{n}{4k}$. If there is 1 orz component, then let $n=4kq+r$ where $1\le r\le 4q$. Assume for contradiction $\alpha \le q$. Then $2E+V=4kn+1$, so $$q\ge \alpha \ge \frac{n^2}{2E+V} = \frac{n^2}{4kn+1}$$ Therefore, $q(4k(4kq+r)+1) \ge (4kq+r)^2$. Expanding, $$\iff q(16k^2q+4kr+1)\ge 16k^2q^2+8kqr+r^2$$ $$\iff q\ge 4kqr+r^2$$ Since $r\ge 1$, this is clearly impossible.

The answer is $\lceil \frac{n}{4k}\rceil$. The construction is as follows: let $n=4kq+r$ where $1\le r\le 4k$. Then the graph $$\underbrace{K_{4k} \sqcup \cdots \sqcup K_{4k}}_q \sqcup K_r$$ works (gives answer of $q+1=\lceil \frac{n}{4k}\rceil$) The general idea is to bound the number of edges, then use Caro-Wei theorem to finish. Some notations: $G[X]$ denoted the induced subgraph of $X$. i.e. a graph $(X,E')$ with vertices in $X$, and two vertices are connected by an edge in $G[X]$ if and only if they are connected by an edge in $G$. $e(A,B)$ is the number of edges with one vertex in $A$ and the other vertex in $B$. We sometimes denote this $c(G)$ if $G=A\sqcup B$. $s(G)$ denote the number of vertices on the same side. That is, if $e(A)$ is the number of edges in $G[A]$, then if we partition $G$ into $A\sqcup B$, then $s(G) = e(A) + e(B)$. [Lemma] If there is a connected component with $V$ vertices and $E$ edges, then the maximum number of crossing edges is at least $\frac{E}{2} + \frac{V-1}{4}$. Furthermore, if $V$ is even, then the maximum number of crossing edges is at least $\frac{E}{2} + \frac{V}{4}$. In other words, if $c$ is the number of crossing edges and $s$ is the number of single-sided edges, then $c-s \ge \frac{V-1}{2}$ [Proof of Lemma] We induct on $V$. If $V$ is even, if we can divide the graph into two sets of vertices $X\sqcup Y$ such that $|X|, |Y|$ are even and $X,Y$ are connected, then we are done because we can partition $X$ into $X_1,X_2$ such that $c_x-s_x\ge \frac{|X|}{2}$, and partition $Y$ into $Y_1,Y_2$ such that $c_y-s_y\ge \frac{|Y|}{2}$. Then $(X_1\cup Y_1), (X_2\cup Y_2)$ or $(X_1\cup Y_2),(X_2\cup Y_1)$ works. If I partition $G$ into $X_1\cup Y_1, X_2\cup Y_2$, then $c-s$ is $$\frac{|X|+|Y|}{2} + e(X_1,Y_2) + e(X_2, Y_1) - e(X_1,Y_1) - e(X_2,Y_2)$$ On the other hand, if I partition $G$ into $X_1\cup Y_2, X_2\cup Y_1$, then $c-s$ is $$\frac{|X|+|Y|}{2} + e(X_1,Y_1) + e(X_2, Y_2) - e(X_1,Y_2) - e(X_2,Y_1)$$ So at least one of the two ways of coloring works. Consider a tree where $v$ is adjacent to all neighbours in $G$. Call the neighbours $n_1,\cdots,n_l$. If some $n_j$ subtree in the spanning tree (call $T_j$) has even size, then letting $X$ be the vertices of $T_j$ works. Otherwise, if all $n_j$ subtrees have odd size, then if there is a crossing edge (in $G$) between $n_j, n_m$ then taking $X$ to be $T_j \sqcup T_m$ works. Otherwise, there are no crossing edge between $n_j,n_m$ for all $n_j,n_m$. This implies that $l$ is odd. For each $n_j$ subtree (say with $f_j$ vertices), I can partition it such that $c(n_j)-s(n_j) \ge \frac{f_j-1}{2}$. After doing that I make all neighbours of $v$ in the same group and $v$ in the other group. If $V$ is odd, then (*) works much more easily (taking a vertex or any $T_j$ gives what we want). [Lemma 2] If $V$ is odd, equality only holds when $G$ is the union of a bunch of (maximal as size cannot be increased) cliques of odd size (call $L_1, L_2, \cdots, L_m$), where two distinct cliques intersect at at most one vertex, and there are no crossing edges between $L_j$ and $L_l$ for any $1\le j<l\le m$. In other words, each edge is in a maximal clique (which always have an odd number of vertices). Furthermore, there does not exist cliques $L_{j_1}, \cdots, L_{j_l}, L_{j_{l+1}} = L_{j_1}$ such that $L_{j_p} L_{j_{p+1}}$ intersect at a vertex, unless the vertex is the same vertex. Proof of Lemma 2 Call a graph orz if equality holds for that graph (it is clear that the condition described here is sufficient, we need to show it is necessary). We call a graph satisfactory if it meets all criteria in lemma 2. We induct on $|V|$ to show that all orz graphs with $|V|$ vertices ($|V|$ odd) are satisfactory. For smaller $|V|$, orz and satisfactory mean the same thing. Note this means if I partition our vertices into $X,Y\ne \emptyset$, where $|X|$ is odd and $G[X], G[Y]$ are connected, then $G[X]$ is orz and there are an even number of crossing edges. This is true because otherwise, by inductive hypothesis, since $X$ is connected and $G[X] $ is not orz, I can partition $X$ into $X_1\sqcup X_2$ such that $c(X)-s(X) \ge \frac{|X|+1}{2}$. By lemma 1, since $Y$ is connected, I can partition $Y$ into $Y_1\sqcup Y_2$ such that $c(Y)-s(Y) \ge \frac{|Y|}{2}$. Then if I partition $G$ into $X_1\cup Y_1, X_2\cup Y_2$, then $c-s$ is $$\frac{|X|+|Y|+1}{2} + e(X_1,Y_2) + e(X_2, Y_1) - e(X_1,Y_1) - e(X_2,Y_2)$$ On the other hand, if I partition $G$ into $X_1\cup Y_2, X_2\cup Y_1$, then $c-s$ is $$\frac{|X|+|Y|+1}{2} + e(X_1,Y_1) + e(X_2, Y_2) - e(X_1,Y_2) - e(X_2,Y_1)$$ Here, recall $e(A,B)$ is the number of edges with one vertex in $A$ and the other vertex in $B$. One of these two is at least $\frac{|X|+|Y|+1}{2}=\frac{|V|+1}{2}$, so equality does not hold. Therefore, when if I partition our vertices into $X,Y\ne \emptyset$, where $|X|$ is odd and $G[X], G[Y]$ are connected, then $G[X]$ is orz=satisfactory, and $e(X,Y)$ is even. Step 1: Show that there exists a satisfactory subgraph. i.e. there exists $E'\subset E$ such that $G(V,E')$ is satisfactory. Again, construct a BFS tree from $v$, the vertex with maximum degree. Let the subtrees be $T_1,\cdots,T_m$. If $m=2$ then our graph is a cycle and it is easy to check equality can only be achieved for $C_3 \cong K_3$. Otherwise, $m\ge 3$. For all $j$, if $T_j$ has an odd number of vertices, $G[T_j]$ is orz. Otherwise, $G[V\backslash T_j]$ is orz. If $G[V\backslash T_j]$ is orz for any $j$, then say $$G[V\backslash T_j] = L_1 \cup \cdots \cup L_m$$ We pick $Y$ in our partition carefully. We consider a process starting on $L_{x_0}$ where $x_0=1$. If $L_1$ shares a vertex $w$ with $L_{x_1}$ for some $x_1$, then we go to $L_{x_1}$. Then, if $L_{x_1}$ doesn't contain a shared vertex other than $w$, we take $Y = L_{x_1}\backslash \{w\}$. Otherwise, it contains a shared vertex other than $v$ with $L_{x_2}$ for some $x_2$. At $x_j$, if it has a shared vertex with some $L_{x_{j+1}}$ then we go to $L_{x_{j+1}}$. By the definition of orz, I cannot visit the same clique twice (since my first two steps visit two different vertices (in the intersection at least two shared cliques) already. Therefore, this process must end. When it ends, say I am at $L_m$, and it has only one shared vertex, call $w$. Then picking $Y=L_m\backslash \{w\}$ satisfy $G[V\backslash Y]$ is connected. Note $|Y|$ is even, so $|V\backslash Y|$ is odd. This implies $G[V\backslash Y]$ is also orz=satisfactory. Since $G[V\backslash Y]$ is orz, $G$ can be seen as adding a clique $L_m$ to $\{w\}$, so $G$ contains an satisfactory subgraph (with all vertices). To prove the existence of a satisfactory subgraph (with all vertices), it remains to deal with the case where $|T_j|$ is odd for all $j$. This implies that $G[T_j]$ is orz. Case 1: There exists $j<l$, and an edge between a vertex in $T_j$ and another vertex in $T_l$. Then note $T_j\sqcup T_l, V\backslash (T_j\sqcup T_l)$ are both connected. Since $|T_j\sqcup T_l|$ is even, $G[V\backslash (T_j\sqcup T_l)]$ is orz. We proceed like the previous case to show that $G$ contains an orz subgraph. Case 2: For all $j,l$ there doesn't exist a vertex in $T_j$ and another vertex in $T_l$. Since $m\ge 3$ we can show that $G$ is not orz by lemma 1. Now for step 2: [A satisfactory subset of edges on an orz graph implies graph is satisfactory] Suppose there is an edge between $v_1v_2$ where $v_1\in V\backslash L_m, v_2\in Y$. Then there must be at least two crossing edges, since the number of crossing edges between $Y$ and $V\backslash Y$ must be even, and there are an even number of edges that involve $w$. Therefore, there is another edge $v_3v_4$ where $v_1\in V\backslash L_m, v_2\in Y$. WLOG, $v_3\ne v_1$. If $v_1$ is not in the intersection of two cliques in the orz induced subgraph $G[V\backslash Y]$, then we take $G=X'\sqcup Y', Y' = \{v_1,v_2\}$. Then note $X'$ is connected, so $G[X']$ is orz. In particular, $v_3,v_4$ must be in the same clique. Say $v_3$ is in $L_j$ in $G[(V\backslash L_m)\cup \{v\}]$ and any path from a vertex in $L_j$ to $w$ needs to go through $L_{j_1}, \cdots, L_{j_t}$ to get to $w$ (note this sequence is unique). Then I claim $G[L_j\cup L_{j_1}\cup \cdots \cup L_{j_t} \cup L_m]$ is a clique. This suffices because if I view this as a process of merging cliques, note that all resulting clique sizes are odd, and the number of cliques decrease, so in the end, I get a satisfactory graph. Let $L$ be the clique containing $v_3$ and $v_4$. Then I can go to $v_3v_4$ via $L$ or via this sequence of cliques, contradicting our assumption that $G[X']$ is orz=satisfactory. We do need to show that $L$ doesn't intersect with any vertices outside of $G[L_j\cup L_{j_1}\cup \cdots \cup L_{j_t} \cup L_m]$ Now we are done edge bounding, and we go back to bounding the size of the maximal independent set. We now introduce a useful lemma: [Caro-Wei's theorem] $\alpha(G) \ge \sum_{v} \frac{1}{d(v)+1}$. By convexity, $\alpha(G) \ge \frac{V(G)^2}{2E(G)+V(G)}$ Sketch of proof: For each vertex, give it a weight of $\frac{1}{d+1}$. Continually remove the vertex with minimal degree; the weight decreases by at most 1 each step. [Smoothing] It can be easily proven that the chromatic number of a orz graph $L_1\cup L_2\cup \cdots \cup L_m$ is $m$, by noting there is a clique with two unshared vertices and inducting. If $t\ne u$, the graph have a $K_{2t+1}$, and a $K_{2u+1}$ that intersect at at most one vertex, I can replace them with two $K_{t+u+1}$ components (that intersect at one vertex if they previously did). This monotonically decreases the number of crossing edges because $t(t+1)+u(u+1) \ge (\frac{t+u+1}{2})^2$ when $|t-u|\ge 2$. From this, we can assume that all components where the maximum number of crossing edges is $\frac e2 + \frac{v-1}{4}$ is $K_{2t+1}$ The final blow Say there are $m$ disjoint copies of $K_{2t+1}$. Then the induced subgraph of vertices not in these copies has at least $n-m(2t+1)$ vertices. Furthermore, the maximum number of crossing edges for that induced subgraph is $kn - mt(t+1)$, so $2E+V$ (for that subgraph) is at most $4(kn - mt(t+1))$. Since $\frac{v^2}{2e+v}$ is increasing in $v$, we assume there are $n-m(2t-1)$ vertices. We want to show that the largest independent set of that induced subgraph is at least $\frac{n}{4k}-m$. We know by Caro-Wei that it is at least $$\frac{(n-m(2t+1))^2}{4(kn - mt(t+1))}$$So we want to show that $$\frac{(n-m(2t+1))^2}{kn - mt(t+1)} \ge \frac nk - 4m$$Since everything is positive, this is equivalent to $$(n-m(2t+1))^2 \ge (\frac nk - 4m)(kn - mt(t+1))$$ Sub $u=2t+1$, then this is same as $$(n-mu)^2 \ge \left(\frac nk - 4m\right)\left(kn - m\frac{u^2-1}{4}\right)$$ $$\iff (n-mu)^2 \ge \left(\frac nk - 4m\right)\left(kn - m\frac{u^2}{4}\right) + \left(\frac nk - 4m\right)\frac m4$$ $$\iff -2nmu \ge -4mkn - m\frac{u^2n}{4k} + \left(\frac nk - 4m\right)\frac m4$$ $$\iff \left(\sqrt{4mkn}-u\sqrt{\frac{mn}{4k}}\right)^2 \ge \left(\frac nk - 4m\right)\frac m4$$ Since $u$ is an odd positive integer, this is minimized when $u=4k\pm 1$. In this case, we need to show $$\frac{mn}{4k} \ge \left(\frac nk - 4m\right)\frac m4$$ Which is obvious by expansion.

The answer is $\lceil \frac{n}{4k}\rceil$. The construction is as follows: let $n=4kq+r$ where $1\le r\le 4k$. Then the graph $$\underbrace{K_{4k} \sqcup \cdots \sqcup K_{4k}}_q \sqcup K_r$$ works (gives answer of $q+1=\lceil \frac{n}{4k}\rceil$) The general idea is to bound the number of edges, then use Caro-Wei theorem to finish. Some notations: $G[X]$ denoted the induced subgraph of $X$. i.e. a graph $(X,E')$ with vertices in $X$, and two vertices are connected by an edge in $G[X]$ if and only if they are connected by an edge in $G$. $e(A,B)$ is the number of edges with one vertex in $A$ and the other vertex in $B$. We sometimes denote this $c(G)$ if $G=A\sqcup B$. $s(G)$ denote the number of vertices on the same side. That is, if $e(A)$ is the number of edges in $G[A]$, then if we partition $G$ into $A\sqcup B$, then $s(G) = e(A) + e(B)$. [Lemma] If there is a connected component with $V$ vertices and $E$ edges, then the maximum number of crossing edges is at least $\frac{E}{2} + \frac{V-1}{4}$. Furthermore, if $V$ is even, then the maximum number of crossing edges is at least $\frac{E}{2} + \frac{V}{4}$. In other words, if $c$ is the number of crossing edges and $s$ is the number of single-sided edges, then $c-s \ge \frac{V-1}{2}$ [Proof of Lemma] We induct on $V$. If $V$ is even, if we can divide the graph into two sets of vertices $X\sqcup Y$ such that $|X|, |Y|$ are even and $X,Y$ are connected, then we are done because we can partition $X$ into $X_1,X_2$ such that $c_x-s_x\ge \frac{|X|}{2}$, and partition $Y$ into $Y_1,Y_2$ such that $c_y-s_y\ge \frac{|Y|}{2}$. Then $(X_1\cup Y_1), (X_2\cup Y_2)$ or $(X_1\cup Y_2),(X_2\cup Y_1)$ works. If I partition $G$ into $X_1\cup Y_1, X_2\cup Y_2$, then $c-s$ is $$\frac{|X|+|Y|}{2} + e(X_1,Y_2) + e(X_2, Y_1) - e(X_1,Y_1) - e(X_2,Y_2)$$ On the other hand, if I partition $G$ into $X_1\cup Y_2, X_2\cup Y_1$, then $c-s$ is $$\frac{|X|+|Y|}{2} + e(X_1,Y_1) + e(X_2, Y_2) - e(X_1,Y_2) - e(X_2,Y_1)$$ So at least one of the two ways of coloring works. Consider a tree where $v$ is adjacent to all neighbours in $G$. Call the neighbours $n_1,\cdots,n_l$. If some $n_j$ subtree in the spanning tree (call $T_j$) has even size, then letting $X$ be the vertices of $T_j$ works. Otherwise, if all $n_j$ subtrees have odd size, then if there is a crossing edge (in $G$) between $n_j, n_m$ then taking $X$ to be $T_j \sqcup T_m$ works. Otherwise, there are no crossing edge between $n_j,n_m$ for all $n_j,n_m$. This implies that $l$ is odd. For each $n_j$ subtree (say with $f_j$ vertices), I can partition it such that $c(n_j)-s(n_j) \ge \frac{f_j-1}{2}$. After doing that I make all neighbours of $v$ in the same group and $v$ in the other group. If $V$ is odd, then (*) works much more easily (taking a vertex or any $T_j$ gives what we want). [Lemma 2: Characterization of "orz" subgraphs that don't let us immediately finish] If $V$ is odd, equality only holds when $G$ is the union of a bunch of (maximal as size cannot be increased) cliques of odd size (call $L_1, L_2, \cdots, L_m$), where two distinct cliques intersect at at most one vertex, and there are no crossing edges between $L_j$ and $L_l$ for any $1\le j<l\le m$. In other words, each edge is in a maximal clique (which always have an odd number of vertices). Furthermore, there does not exist cliques $L_{j_1}, \cdots, L_{j_l}, L_{j_{l+1}} = L_{j_1}$ such that $L_{j_p} L_{j_{p+1}}$ intersect at a vertex, unless the vertex is the same vertex. Proof of Lemma 2 Call a graph orz if equality holds for that graph (it is clear that the condition described here is sufficient, we need to show it is necessary). We call a graph satisfactory if it meets all criteria in lemma 2. We induct on $|V|$ to show that all orz graphs with $|V|$ vertices ($|V|$ odd) are satisfactory. For smaller $|V|$, orz and satisfactory mean the same thing. Note this means if I partition our vertices into $X,Y\ne \emptyset$, where $|X|$ is odd and $G[X], G[Y]$ are connected, then $G[X]$ is orz and there are an even number of crossing edges. This is true because otherwise, by inductive hypothesis, since $X$ is connected and $G[X] $ is not orz, I can partition $X$ into $X_1\sqcup X_2$ such that $c(X)-s(X) \ge \frac{|X|+1}{2}$. By lemma 1, since $Y$ is connected, I can partition $Y$ into $Y_1\sqcup Y_2$ such that $c(Y)-s(Y) \ge \frac{|Y|}{2}$. Then if I partition $G$ into $X_1\cup Y_1, X_2\cup Y_2$, then $c-s$ is $$\frac{|X|+|Y|+1}{2} + e(X_1,Y_2) + e(X_2, Y_1) - e(X_1,Y_1) - e(X_2,Y_2)$$ On the other hand, if I partition $G$ into $X_1\cup Y_2, X_2\cup Y_1$, then $c-s$ is $$\frac{|X|+|Y|+1}{2} + e(X_1,Y_1) + e(X_2, Y_2) - e(X_1,Y_2) - e(X_2,Y_1)$$ Here, recall $e(A,B)$ is the number of edges with one vertex in $A$ and the other vertex in $B$. One of these two is at least $\frac{|X|+|Y|+1}{2}=\frac{|V|+1}{2}$, so equality does not hold. Therefore, when if I partition our vertices into $X,Y\ne \emptyset$, where $|X|$ is odd and $G[X], G[Y]$ are connected, then $G[X]$ is orz, and $e(X,Y)$ is even. Our proof has two steps: (1) a subset of edges give a satisfactory subgraph. (2) Our graph is satisfactory. Step 1Again, construct a BFS tree from $v$, the vertex with maximum degree. Let the subtrees be $T_1,\cdots,T_m$. If $m=2$ then our graph is a cycle and it is easy to check equality can only be achieved for $C_3 \cong K_3$. Otherwise, $m\ge 3$. For all $j$, if $T_j$ has an odd number of vertices, $G[T_j]$ is orz. Otherwise, $G[V\backslash T_j]$ is orz. If $G[V\backslash T_j]$ is orz for any $j$, then say $$G[V\backslash T_j] = L_1 \cup \cdots \cup L_m$$ We pick $Y$ in our partition carefully. We consider a process starting on $L_{x_0}$ where $x_0=1$. If $L_1$ shares a vertex $w$ with $L_{x_1}$ for some $x_1$, then we go to $L_{x_1}$. Then, if $L_{x_1}$ doesn't contain a shared vertex other than $w$, we take $Y = L_{x_1}\backslash \{w\}$. Otherwise, it contains a shared vertex other than $v$ with $L_{x_2}$ for some $x_2$. At $x_j$, if it has a shared vertex with some $L_{x_{j+1}}$ then we go to $L_{x_{j+1}}$. By the definition of orz, I cannot visit the same clique twice (since my first two steps visit two different vertices (in the intersection at least two shared cliques) already. Therefore, this process must end. When it ends, say I am at $L_m$, and it has only one shared vertex, call $w$. Then picking $Y=L_m\backslash \{w\}$ satisfy $G[V\backslash Y]$ is connected. Note $|Y|$ is even, so $|V\backslash Y|$ is odd. This implies $G[V\backslash Y]$ is also orz=satisfactory. Since $G[V\backslash Y]$ is orz, $G$ can be seen as adding a clique $L_m$ to $\{w\}$, so $G$ contains an satisfactory subgraph (with all vertices). To prove the existence of a satisfactory subgraph (with all vertices), it remains to deal with the case where $|T_j|$ is odd for all $j$. This implies that $G[T_j]$ is orz=satisfactory. Case 1: There exists $j<l$, and an edge between a vertex in $T_j$ and another vertex in $T_l$. Then note $T_j\sqcup T_l, V\backslash (T_j\sqcup T_l)$ are both connected. Since $|T_j\sqcup T_l|$ is even, $G[V\backslash (T_j\sqcup T_l)]$ is orz=satisfactory. We proceed like the previous case to show that $G$ contains a subset of edges $E'$ such that $G(V,E')$ is satisfactory. Case 2: For all $j,l$ there doesn't exist a vertex in $T_j$ and another vertex in $T_l$. Since $m\ge 3$ we can show that $G$ is not orz by lemma 1. Step 2: A satisfactory subset of edges on an orz graph implies graph is satisfactorySuppose in our satisfactory subgraph, $L_m$ contains only vertex that is in $L_j$ for some $j\ne m$. Suppose there is an edge between $v_1v_2$ where $v_1\in V\backslash L_m, v_2\in Y$. Case 1: There is exactly one crossing edge of this form. Then I claim our graph isn't actually orz. We first partition $(V\backslash L_m) \cup \{w\}$ into two parts such that $c-s = \frac{|V| - |L_m| + 1 - 1}{2}$. It is possible to partition $L_m$ into two parts (with $w$ already in place, and to be added to our partition of $(V\backslash L_m) \cup \{w\}$) such that $c(L_m)-s(L_m) = \frac{|L_m|-1}{2}$ and $v_2$ is NOT on the same side as $v_1$. This partition proves our graph is not orz. Case 2: There must be at least two crossing edges between $V\backslash L_m$ and $Y$. Say there is another edge $v_3v_4$ where $v_1\in V\backslash L_m, v_2\in Y$. WLOG, $v_3\ne v_1$. If $v_1$ is not in the intersection of two cliques in the orz induced subgraph $G[V\backslash Y]$, then we take $G=X'\sqcup Y', Y' = \{v_1,v_2\}$. Then note $X'$ is connected, so $G[X']$ is orz. In particular, $v_3,v_4$ must be in the same clique. Say $v_3$ is in $L_j$ in $G[(V\backslash L_m)\cup \{v\}]$ and any path from a vertex in $L_j$ to $w$ needs to go through $L_{j_1}, \cdots, L_{j_t}$ to get to $w$ (note this sequence is unique). Then I claim $G[L_j\cup L_{j_1}\cup \cdots \cup L_{j_t} \cup L_m]$ is a clique. This suffices because if I view this as a process of merging cliques, note that all resulting clique sizes are odd, and the number of cliques decrease, so in the end, I get a satisfactory graph. Let $L$ be the clique containing $v_3$ and $v_4$. Then I can go to $v_3v_4$ via $L$ or via this sequence of (maximal) cliques. If these sequences are different, then we have contradicted our assumption that $G[X']$ is orz=satisfactory. It follows that for the cliques in the path to be maximal cliques, they must be $L$. Satisfactory graphs are orzSuppose in our satisfactory subgraph, $L_m$ contains only vertex that is in $L_j$ for some $j\ne m$. Suppose there is an edge between $v_1v_2$ where $v_1\in V\backslash L_m, v_2\in Y$. Case 1: There is exactly one crossing edge of this form. Then I claim our graph isn't actually orz. We first partition $(V\backslash L_m) \cup \{w\}$ into two parts such that $c-s = \frac{|V| - |L_m| + 1 - 1}{2}$. It is possible to partition $L_m$ into two parts (with $w$ already in place, and to be added to our partition of $(V\backslash L_m) \cup \{w\}$) such that $c(L_m)-s(L_m) = \frac{|L_m|-1}{2}$ and $v_2$ is NOT on the same side as $v_1$. This partition proves our graph is not orz. Case 2: There must be at least two crossing edges between $V\backslash L_m$ and $Y$. Say there is another edge $v_3v_4$ where $v_1\in V\backslash L_m, v_2\in Y$. WLOG, $v_3\ne v_1$. If $v_1$ is not in the intersection of two cliques in the orz induced subgraph $G[V\backslash Y]$, then we take $G=X'\sqcup Y', Y' = \{v_1,v_2\}$. Then note $X'$ is connected, so $G[X']$ is orz. In particular, $v_3,v_4$ must be in the same clique. Say $v_3$ is in $L_j$ in $G[(V\backslash L_m)\cup \{v\}]$ and any path from a vertex in $L_j$ to $w$ needs to go through $L_{j_1}, \cdots, L_{j_t}$ to get to $w$ (note this sequence is unique). Then I claim $G[L_j\cup L_{j_1}\cup \cdots \cup L_{j_t} \cup L_m]$ is a clique. This suffices because if I view this as a process of merging cliques, note that all resulting clique sizes are odd, and the number of cliques decrease, so in the end, I get a satisfactory graph. Let $L$ be the clique containing $v_3$ and $v_4$. Then I can go to $v_3v_4$ via $L$ or via this sequence of (maximal) cliques. If these sequences are different, then we have contradicted our assumption that $G[X']$ is orz=satisfactory. It follows that for the cliques in the path to be maximal cliques, they must be $L$. Now we are done edge bounding. We first do some clique smoothing: Clique smoothingWe do a bunch of operations on the graph such that tries to make some orz components no longer orz, and keep cliques of the same size. Let $m$ be the number of orz components. Case 1: $m\ge 2$ and there exists a maximal clique $L_j$ in one component $C_1$ and another maximal clique $M_t$ in the other component $C_2$ such that $|V(L_j)| > |V(M_t)|$ Let $A$ be a maximal anticlique of Since $|V(L_j)|\ge 5$ and at most one vertex in $L_j$ is in the maximum anticlique of $C_1$, I claim we can "merge" two vertices in $C_1$ such that the maximum anticlique remains. Let $x$ be a vertex in $L_j$, and $v_1,v_2 \in L_j\backslash \{x\}$. We consider a new $C'_1$ as follows: $v_1,v_2$ is contracted into a new vertex $v'$ such that $v'$ is adjacent to whatever vertices originally adjacent to $v_1,v_2$. Then if $S$ is the set of vertices in $C_1$ that is originally in at least two maximal cliques (and edges between two vertices in the same maximal clique), then this operation basically contracts $v_1,v_2$ if $v_1,v_2$ are both in the tree and does nothing otherwise. Therefore, using the same argument as the proof where all satisfactory graphs are orz, we can show that this new connected component $C'_1$ can be partitioned into $X,Y$ such that $c(C'_1)-s(C'-1) = \frac{|C'_1|}{2}$. Of course the maximal anticlique remains. We do something similar on $C_2$: we add a vertex to $M_t$ that increases the size of $M_t$ by 1 (i.e. this vertex is only adjacent to all vertices previously in $M_t$). Clearly, this also doesn't decrease the maximal anticlique, but makes the graph no longer orz. We introduce an important theorem: [Caro-Wei's theorem] $\alpha(G) \ge \sum_{v} \frac{1}{d(v)+1}$. By convexity, $\alpha(G) \ge \frac{V(G)^2}{2E(G)+V(G)}$ Sketch of proof: For each vertex, give it a weight of $\frac{1}{d+1}$. Continually remove the vertex with minimal degree; the weight decreases by at most 1 each step. Case 1: m is at least 2After doing this, let $m$ be the number of orz components. If $m\ge 2$, then all clique sizes of orz components are equal to $u$ for some odd integer $u$. Suppose all clique sizes of orz components are equal to $u$. Final LemmaSuppose $H$ is an orz graph where all cliques have size $u$. Then $|H| \le \alpha(G)u$. Through BFS, we can find a maximal clique $L_t$ with only one vertex $w$ in other maximal cliques. We take a vertex from $L_t\setminus \{w\}$, and delete all vertices in $L_t$. We call this the obliteration of $L_t$ We can write the new graph $G' = L'_1 \cup \cdots \cup L'_q$ where $L'_1$ is what happens to $L_1$ after vertices are removed. All non-obliterated components sizes monotonically decrease, and the hypergraph with vertices in at least two maximum cliques and edges as cliques remains acyclic. Therefore, we get rid of at most $u$ vertices each time, so $|H| \le \alpha(G)u$ Say the disjoint copies of $K_{2t+1}$ have total chromatic number $p$. Then by our lemma the induced subgraph of vertices not in these copies has at least $n-p(2t+1)$ vertices. Furthermore, the maximum number of crossing edges for that induced subgraph is $kn - pt(t+1)$, so $2E+V$ (for that subgraph) is at most $4(kn - pt(t+1))$. Since $\frac{v^2}{2e+v}$ is increasing in $v$, we assume there are exactly $n-p(2t-1)$ vertices. We know by Caro-Wei that it is at least $$\frac{(n-p(2t+1))^2}{4(kn - pt(t+1))}$$So we want to show that $$\frac{(n-m(2t+1))^2}{kn - pt(t+1)} \ge \frac nk - 4p$$Since everything is positive, this is equivalent to $$(n-p(2t+1))^2 \ge \left(\frac nk - 4p\right)(kn - pt(t+1))$$Sub $u=2t+1$, then this is same as $$(n-pu)^2 \ge \left(\frac nk - 4p\right)\left(kn - p\frac{u^2-1}{4}\right)$$ $$\iff (n-pu)^2 \ge \left(\frac nk - 4p\right)\left(kn - p\frac{u^2}{4}\right) + \left(\frac nk - 4p\right)\frac p4$$ $$\iff -2npu \ge -4pkn - p\frac{u^2n}{4k} + \left(\frac nk - 4p\right)\frac p4$$ $$\iff \left(\sqrt{4pkn}-u\sqrt{\frac{pn}{4k}}\right)^2 \ge \left(\frac nk - 4p\right)\frac m4$$ Since $u$ is an odd positive integer, this is minimized when $u=4k\pm 1$. In this case, we need to show $$\frac{pn}{4k} \ge \left(\frac nk - 4p\right)\frac p4$$ Which is obvious by expansion. Case 2: m is 0 or 1It remains to deal with the case where there is 0 or 1 orz component. If there are 0 orz components, then $2E+V\le 4kn$ in our original graph $G$, so $\alpha(G) \ge \frac{V^2}{2E+V} = \frac{n}{4k}$. If there is 1 orz component, then let $n=4kq+r$ where $1\le r\le 4q$. Assume for contradiction $\alpha \le q$. Then $2E+V=4kn+1$, so $$q\ge \alpha \ge \frac{n^2}{2E+V} = \frac{n^2}{4kn+1}$$ Therefore, $q(4k(4kq+r)+1) \ge (4kq+r)^2$. Expanding, $$\iff q(16k^2q+4kr+1)\ge 16k^2q^2+8kqr+r^2$$ $$\iff q\ge 4kqr+r^2$$ Since $r\ge 1$, this is clearly impossible.

Solved with Jeff Chen and Espen Slettnes. The answer is \(\lceil n/4k\rceil\). Upper bound: Let \(G\) consist of \(\lceil n/4k\rceil\) disjoint cliques each of size either \(4k\) or \(4k-1\). Then each independent set has size at most \(\lceil n/4k\rceil\). Moreover, if \(G\) is partitioned into two parts, then one part has at most \(n/2\) vertices, and each vertex has at most \(2k\) edges connecting it to the other part, so the number of edges between the two parts is at most \(n/2\cdot 2k=kn\). Construction: We now show every such graph \(G\) has an independent set of size at least \(n/4k\). Greedily select independent sets \(S_1\), \(S_2\), \(\ldots\) so that for each \(i\), \(S_i\) is chosen as the largest possible independent set not intersecting \(S_1\), \(\ldots\), \(S_{i-1}\). If \(|S_i|<n/4k\) for each \(i\), then \(|S_1|+\cdots+|S_{2k}|<n/2\). But by construction, each of the remaining vertices outside of \(S_1\), \(\ldots\), \(S_{2k}\) is connected to at least one vertex in each of \(S_1\), \(\ldots\), \(S_{2k}\). Then if we partition \(G\) so that one part is \(S_1\sqcup\cdots\sqcup S_{2k}\), the number of edges between the two parts is more than \(2k\cdot n/2=kn\), contradiction.