# Is it possible to start with a partially colored graph for a graph $G$ and complete it into a coloring with $\chi(G)$ colors?

I was trying this problem: A question about graph coloring and partition of graph

and had an idea which is:

We know that $$\chi(G[X])\le k$$ and $$\chi(G[Y])\le k$$. and $$E(X,Y)\le k-1$$. Color $$X$$ in $$G[X]$$ using k colors, say$$\{1,2,...,k\}$$. Then connect the two partion with the $$k-1$$ edges between them. Because a vertex in $$Y$$ has at most $$k-1$$ neighbours in $$|X|$$, It is adjacent to at most $$k-1$$ different colored vertices. So pick a vertex $$v_1$$ in $$Y$$ whose number of neighbors in $$X$$ is the maximum among all vertices in $$Y$$. It is adjacent to at most $$k-1$$ colored vertices so we can color it using the one of $$\{1,2...,k\}$$. Now pick another vertex $$v_2$$ in $$Y$$ with neighbour in $$|X|$$ maximum among all vertices in $$X-\{v_1\}$$, It is adjacent to at most $$k-2$$ edges in $$X$$(because $$v_1$$ is adjacent to at least one in $$X$$). It could also be adjacent to $$v_1$$, but in any case, it has at most $$k-1$$ colored neighbors, so then you can color it using one of $$\{1,2,...,k\}$$. Keep this coloring process going until you colored all vertices in $$Y$$ with neighbours in $$X$$. Now it would be nice if we can complete this partial coloring into a coloring using $$\chi(G[Y])$$ colors. Because then that solves the problem.

• If you look at the graph in the shape $N$, this is bipartite and hence $2$-colorable, but if you color the upper right corner and the lower left corner with the same color, you can't extend this to a $2$-coloring. – Matt Samuel Nov 20 '18 at 0:00
• If the answer to the title question were "yes", it would be really easy to determine the chromatic number of any graph; the greedy algorithm would always produce an optimal coloring. – bof May 11 at 5:24