2
$\begingroup$

I have simple graph G on 10 vertices the degree of each vertex is 8. I need to determine the chromatic number of G. I tried drawing and all but it seems there is a trick needs to be used.

$\endgroup$
5
$\begingroup$

Let $G = (V, E)$ be a simple graph like you described (which is unique up to isomorphism and known as the Turán graph $T(10, 5)$, by the way). Note that the maximal degree possible in a graph with $10$ vertices is $9$ and thus, for every vertex $v$ in $G$ there exists a unique vertex $w \ne v$ which is not connected to $v$ and the two vertices share a neighborhood, i.e. $N(v) = N(w)$. Therefore, $v$ and $w$ may be colored using the same color. This however implies that the chromatic number of $G$, denoted by $\chi(G)$, satisfies $\chi(G) \leq 5$ since we can take all such pairs $\{v, w\}$ as described above and assign every such pair a unique color (using 5 colors in total).

To see that $\chi(G)$ cannot be less than $5$ consider the (induced) subgraph $G'$ of $G$ that we get by removing one vertex of every such pair $\{v, w\}$ as described above (that means $vw \notin E$). We find that $G'$ consists of 5 vertices and is complete, therefore implying that $G$ contains a clique of size $5$ and giving us $\chi(G) \geq 5$.

Hence we have shown $\chi(G) = 5$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry, but I do not understand what you mean here. As I remarked briefly, $G$ is isomorphic to the Turán graph $T(10, 5)$ which has chromatic number 5. $\endgroup$ – Watercrystal May 31 at 17:48
2
$\begingroup$

Let $v$ be some node. then it had 8 neighbors, and there is exactly one node $u$ which is not connected to $v$. Notice that also $u$ has 8 neighbors, and thus $v$ is the only node not neighboring it.

We can partition the graph into 5 groups of 2 nodes $V_1=\{v_1,u_1\},...,V_5=\{v_5,u_5\}$, where every group's node's are not connected to each other (there is no edge $(v_i,u_i)$) but they are connected to everything else.

This is a 5-partition of the graph, and we can give a different color for each pair. Thus the chromatic number satisfies $\chi (G) \le 5$. But if we use less than 5 colors, say, 4 colors, then there must be two groups with a node that has the same color in both, but since that they are connected we get a contradicton to the coloring. Thus $\chi (G) \ge 5$ and finally $\chi (G) =5$


From here, it is a solution to the clique number, and not the chromatic number:

Since we have 5 groups, Then choosing one node from each group guarantees to give us a clique of size 5. So if we define $\omega (G)$ to be its chromatic number, then in this case we have proven that $\omega (G) \ge 5$.

Lets assume toward contradiction that $\omega (G) > 5$. Then there exists a clique of size at least 6. Let that clique be $\{w_1,..,w_6\}$. From the pigeonhole principle, we have that there are two $w_i, w_j$ in the same $V_k$. But then there is no edge between them, in contradiction that this is a clique.

Thus $\omega (G) \le 5$ and finally combining those two together we have $\omega (G)=5$

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The second part of this argument is not correct: the chromatic number is not a lower bound for the clique number of a graph. An example that demonstrates this is any odd cycle of size at least 5: They have chromatic number 3 but no cliques of size 3 (or larger). Also, the chromatic number of $G$ is usually denoted by $\chi(G)$ whereas $\omega(G)$ is used for its clique number. $\endgroup$ – Watercrystal May 31 at 17:23
  • $\begingroup$ to my understanding, its the maximal clique size in a graph... isnt it? $\endgroup$ – nir shahar May 31 at 17:24
  • $\begingroup$ OHHhh i see..... i have misunderstood it $\endgroup$ – nir shahar May 31 at 17:24
  • $\begingroup$ yea sorry i will fix it (even though its nice i found the clique number) $\endgroup$ – nir shahar May 31 at 17:25
  • $\begingroup$ now its supposed to be correct (with the nice addition of clique number proof) $\endgroup$ – nir shahar May 31 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.