0
$\begingroup$

$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

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

$\endgroup$

bumped to the homepage by Community yesterday

This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.

0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.