1
$\begingroup$

Let $G$ be the graph on vertex set $\{1,2,3,4,5,a,b,c,d\}$ where the edges between numbered vertices come from $C_5$ (simple cycle of length), the edges between lettered vertices come from $K_4$ and we take all possible edges of the form $xy$ where $x$ is a number and $y$ is a letter.
What is the chromatic number of $G$? Give a coloring which witnesses the chromatic number and prove that there is no proper coloring with a smaller number of colors.

Before that there was other question where they asked for the largest degree of a vertex, largest size of a clique and the largest size of an independent set. And I manage to solve those parts with the largest degree of a vertex is $8$, the largest size of a clique is $6$ and the largest size of an independent set is $3$. But I was confused with the last part which I mention above because it contain so many edges to trace out by drawing.

I figure out each numbered vertices has $6$ edges with $\{a,b,c,d\}$ and two other numbers like for $1$ it is $\{2,5\}$. And each lettered vertices has $8$ edges with $\{1,2,3,4,5\}$ and rest of lettered vertices.

Is there any relation between graph coloring with those things, as I guess chromatic number highly depend on the clique size (same effect as complete graph)? How to get the chromatic number for $G$?

$\endgroup$
1

2 Answers 2

2
$\begingroup$

The graph $G$ is what is commonly known as the join of two graphs. In this case it is the join of the cycle graph $C_5$ and the complete graph $K_4$. The chromatic number of the join of two graphs is equal to the sum of the two chromatic numbers. In this case the chromatic number of $C_5$ is $3$ and the chromatic number of $K_4$ is $4$, so the answer is $7$.

This argument doesn't give the coloring, but it gives a clue as to how to find it. No color can appear on the $C_5$ part and in the $K_4$ part. So we can color them independently. Coloring $C_5$ with $3$ colors is not hard and coloring $K_4$ with $4$ colors is even easier.

$\endgroup$
4
  • $\begingroup$ I see, I haven't known that yet(+1). Didn't we ignore those extra edges form $xy$ where $x$ is a number and $y$ is a letter? @HeroToRelax And what they mean by Give a coloring which witnesses the chromatic number and prove that there is no proper coloring with a smaller number of colors. $\endgroup$ Apr 7, 2021 at 16:47
  • $\begingroup$ @WhyGraph_ No, when you ignore that I think they call that operation disjoint union. en.wikipedia.org/wiki/Graph_operations $\endgroup$
    – Asinomás
    Apr 7, 2021 at 16:50
  • $\begingroup$ Ahaa, your edited answer clear my confusion. Thanks @HeroToRelax $\endgroup$ Apr 7, 2021 at 16:55
  • $\begingroup$ Glad to hear that. $\endgroup$
    – Asinomás
    Apr 7, 2021 at 16:55
1
$\begingroup$

The chromatic number of the cycle is $3$, and the chromatic number of the $K_4$ is $4$. Since every letter is adjacent to every number, we can't share a color between the cycle and the $K_4$, so we need $7$ colors.

$\endgroup$

You must log in to answer this question.

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