Krdytkyu

Let $G$ be a graph with $2k$ vertices and $k^2$ edges, $kgeq 1$, such that $G$ contains $K_{k-i, k+i}$ as a subgraph, where $0leq i leq k-1$.

Suppose that the complete bipartite subgraph $K_{k-i, k+i}$ has a bipartition $A_1cup A_2$, where $|A_1|=k-i$ and $|A_2|=k+i$. We define
$$P(G, A_1, A_2, 5)={ text{$5$-(vertex) colorings of $G$ such that every vertex of $A_1$ is color $1$ or $2$ and every vertex of $A_2$ is color $3,4$, or $5$} }.$$

I want to show that for any such graph $G$ we have
$$P(G, A_1, A_2, 5) leq 6^k.$$

***If for whatever reason the bound $6^k$ is too small, I am also content with obtaining an upper bound of $6^k+ o(6^k)$.

I thought that perhaps I could prove this claim by induction on $0leq ileq k-i$. One nice observation I have made is that the parameter $P(G, A_1, A_2, 5)$ satisfies a deletion-contraction identity, just as the chromatic polynomial does. That is,
$$P(G, A_1, A_2, 5)=P(G-e, A_1, A_2, 5)-P(G/e, A_1, A_2, 5),$$
for any $ein E(G)$.

Alright, so here is my base case: Suppose $i=1$. Then $K_{k-1,k+1}$ is a subgraph of $G$ which means that there is one edge $e$ in $G$ whose vertex ends are both in $A_1$ or both in $A_2$.

Case 1: Both ends of $e$ are in $A_1$.

We have
$$P(G, A_1, A_2, 5)=P(G-e, A_1, A_2, 5)-P(G/e, A_1, A_2, 5)$$
$$=2^{k-1}3^{k+1}-2^{k-2}3^{k+1} $$
$$=2^{k-2}3^{k+1}=6^k(3/4)<6^k.$$

Case 2: Both ends of $e$ are in $A_2$.

We have
$$P(G, A_1, A_2, 5)=P(G-e, A_1, A_2, 5)-P(G/e, A_1, A_2, 5)$$
$$=2^{k-1}3^{k+1}-2^{k-1}3^{k} $$
$$=2^{k-1}3^{k}(3-1)=6^k.$$

Thus, the bound holds when $i=1$.

I am struggling a lot with the inductive case. If I know that $K_{k-i, k+i}$ is a subgraph of $G$ then there are $i^2$ edges in $G$ that are not in $K_{k-i, k+i}$. Each of these edges must have both ends in $A_1$ or in $A_2$. I can't seem to get the inductive hypothesis to "pop out".

Any help is immensely appreciated. Thank you.