# graph vertex chromatic number in a union of 2 sub-graphs

$G_1$ is graph on the set of vertices $\{1,2,3,4,5,6,7,8\}$, $G_1$ vertice 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$ vertice chromatic number is 7.

we know $G_1$ and $G_2$ have an edge between vertice 7 and vertice 8. (we already used 2 differnt 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\}$, that it's set of edges is the union of the edges set of $G_1$ with the edges set of $G_2$.

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

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 vertice that doesn't connect to a different vertice. (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 it's vertices in the same color.

we go through vertices 1-6, and color each vertice 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).

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.