0
$\begingroup$

Determine the edge-chromatic number of the next graph.

enter image description here

For Vizing`s Theorem $\chi'(G)=4$ or $\chi'(G)=5$. I have try show that $\chi'(G)=4$ but I cannot do it. I think that $\chi'(G)=5$ and I suppose that G has a proper edge coloring with 4 colors, but I dont find a contradiction.

Could you give me any advice or recommendation?

$\endgroup$
2
  • $\begingroup$ Is the absent edge in the bottom-left corner on purpose? (i.e. this graph has order 13 and size 23, right?) $\endgroup$
    – Paralyzed_by_Time
    Jun 8, 2020 at 22:09
  • $\begingroup$ No, It has this edge. I already corrected it $\endgroup$
    – Carlos Andres Henao Acevedo
    Jun 8, 2020 at 22:22

2 Answers 2

Reset to default
2
$\begingroup$

I think I can do it with $4$ colors. I don't have a quick way to make a diagram, so I'll try to explain in words. (It would be easier if you had labelled the vertices.) I'll use the colors Red, Green, Blue and White.

Color one side of the outer triangle R, another side B, and the third side G. Color each side of the smaller triangles the same color as the parallel side of the big triangle. Now we color the $4$ segments on the line from each vertex of the big triangle to the center alternately W and X where X is the color of the side opposite this vertex. We start with W at the outer vertex and end with X at the center. Since X takes the values R,G,B, the edges that meet at the center are different colors.

$\endgroup$
1
  • $\begingroup$ Yep, you're totally right. I was nearly certain the graph was class 1, but couldn't find a coloring in the past 20 mins for the life of me. Well done! $\endgroup$
    – Paralyzed_by_Time
    Jun 8, 2020 at 22:47
1
$\begingroup$

Thanks saulspatz, your coloring is in the next picture

**enter image description here**

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .