[Math] Graph vertex chromatic number in a union of 2 sub-graphs

coloringgraph theory

$G_1$ is graph on the set of vertices $\{1,2,3,4,5,6,7,8\}$, $G_1$ vertex chromatic number is 5.

$G_2$ is graph on the set of vertices $\{7,8,9,10,11,12,13,14,15,17,18,19,20\}$, $G_2$ vertex chromatic number is 7.

We know $G_1$ and $G_2$ have an edge between vertex 7 and vertex 8. (We already used 2 different colors on them both).

$G$ is graph on the set of vertices $\{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20\}$, and its set of edges is the union of the edges set of $G_1$ with the edges set of $G_2$.

The vertex chromatic number of $G$ is: 5 / 7 / 12 / we can't know without further information

Prove the answer.

I think I got it, can someone approve?

After the union to $G$, we copy the colors of $G_2$ to 7,8,9,10,11,12,13,14,15,16,17,18,19,20, obviously, $G$ vertex chromatic number is 7 and can't be less.

We go through the vertices 1,2,3,4,5,6,7,8.

We look for a vertex that doesn't connect to a different vertex. (There must be one, because if only one edge was missing in $G_1$, our chromatic number of $G_1$ was 7, but it's 5).

Once we find a missing edge, we color both its vertices in the same color.

We go through vertices 1-6, and color each vertex that doesn't have a color, with the colors of $G_2$ that we didn't use in $G_1$ (there should be 4-5 of them).

Best Answer

So if I understand correctly, your proof is:

  • We must use at least $7$ colors to color $G$, since it has the subgraph $G_2$, which has chromatic number $7$.
  • We pick some $7$-coloring of $G_2$.

  • Using those colors, we color two non-adjacent vertices in $G_1$ the same color. (There must be a non-edge in $G_1$ for $G_1$ to be $5$-colorable.)

    • If the two non-adjacent vertices in $G_1$ don't include $7$ or $8$, then we have colored $4$ vertices in $G_1$ with $3$ colors, leaving $4$ vertices to be colored with $4$ remaining colors.
    • If the two non-adjacent vertices in $G_1$ include $7$ or $8$, then we have colored $3$ vertices in $G_1$ with $2$ colors, leaving $5$ vertices to be colored with $5$ remaining colors.

    Either way, we can easily color the remaining vertices in $G_1$.

  • Thus we have a $7$-coloring, and $G$ has chromatic number $7$.

It's long, but it works.

A shorter way is to find colorings of $G_1$ and $G_2$, then modify one of them so that vertices $7$ and $8$ receive the same color in both.

Related Question