# 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$$ 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

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).

• Oh, I just noticed your other question Graph theory: graph coloring quesiton; same problem but a different attempt. Well, anyway, I hope my answer helps. Jul 7, 2014 at 10:43
• There is no such word as vertice. The word vertices is the plural of vertex.
– bof
Jul 24, 2020 at 1:08

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.