Graph theory: graph coloring quesiton

348 Views Asked by At

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

As I understand, no vertice of $G_1$ can be connected to a vertice of $G_2$, except vertices 7 and 8, if we use 7 different colors on $G_2$, with vertice 7 and vertice 8 counted as 2 of them, and we use 5 colors on $G_1$ (with vertice 7 and vertice 8, counted as the same colors we used to color $G_2$ ) $G$ must have a vertice chromatic number of 7.

too simple in my opinion, I'm already waiting for my mistake.

2

There are 2 best solutions below

0
On

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$ edge chromatic number is 7 and can't be less.

we go through the edges 1,2,3,4,5,6,7,8

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

once we find a missing vertice, we color both it's edges in the same color.

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

4
On

If the edges $1,\ldots ,20$ are $$ab,bc,cd,ed,fd,gd,hd,id,jd,kd,ld,md,mn,no,op,pq,qr,rs,st,$$ then $G$ has edge-chromatic number $12$. If they are $$ab,ac,ad,ae,af,fg,gh,hi,ji,ki,li,mi,ni,oi,op.pq,qr,$$ the $G$ has edge.chromatic number $7$. In other words: We cannot know. It is also possible to produce examples where $7$ and $8$ have no vertex in common.