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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Matt Samuel Nov 20 '18 at 0:00
  • $\begingroup$ 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. $\endgroup$ – bof May 11 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.