# Graph theory: graph coloring quesiton [duplicate]

$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

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.

• ok I got this: when 7 and 8 degree is 1, G number will be 7. when 7 and 8 will be (4 degree from $G_1$ and 6 degree from $G_2$, then what?) – Seth Keno Jul 6 '14 at 16:51
• I think it's 7 can someone tell me why? – Seth Keno Jul 6 '14 at 17:08
• I don't understand "we know $G_1$ and $G_2$ have a vertice between edge 7 and 8. (we already used 2 different colors on them both)". Doe you mean that that 7 and 8 have a vertex in common? Is this an additional given information, or do you think you can conclude that from the other givens? – Hagen von Eitzen Jul 6 '14 at 18:26
• they should have a vertex in common after the union to G, before that we should look at it as a different vertex I think. it is an additional information given, in the original question the information was ($G_1$ and $G_2$ don't have a vertex between their 7th and 8th edge). – Seth Keno Jul 6 '14 at 18:45

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

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.

• by $ab$ you mean that there is a vertex between edge 1 and 2? if so I don't understand, you can play with $G$ colors after the union to find a smaller edge chromatic number no? no lees then 7 because of $G_2$ – Seth Keno Jul 6 '14 at 18:51
• sorry, every place I wrote edge I meant vertice, and every place I wrote vertice I meant edge in my original question, that's why your answer didn't make sense to me, my bad. we need to find the vertex chromatic nummber – Seth Keno Jul 6 '14 at 18:59
• I fixed my question – Seth Keno Jul 6 '14 at 19:04