# What is the chromatic number of $G$?

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

• Apr 7, 2021 at 16:42

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.
• 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. Apr 7, 2021 at 16:47
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.