5
$\begingroup$

Let the vertices of the graph G be the numbers 1, 2, ..., 100, and two (different) vertices be adjacent if and only if at least one of 2, 3, or 5 is a common divisor of the respective numbers. Determine χ(G), the chromatic number of the graph G.

I tried to solve and got that all even numbers i.e 2,4,6,...,100 form a clique of size 50. And that all prime numbers are isolated so they do not matter in coloring. But I cannot show chromatic number is 50. Any suggestions?

Improve this question
$\endgroup$
3
  • $\begingroup$ All even numbers form a clique, as they have $2$ as a common divisor. You will need at least $51$ colors. $\endgroup$
    – Eric_
    Jun 9 at 16:29
  • $\begingroup$ HOW? Number of even numbers are 50 not 51 $\endgroup$
    – Ibrakhim Tolobekov
    Jun 9 at 16:33
  • $\begingroup$ In addition to the 25 prime numbers, there are 4 other isolated vertices: 1, 49, 77, 91. $\endgroup$
    – Stef
    Jun 9 at 21:33

1 Answer 1

Reset to default
5
$\begingroup$

Hint 1:

Show that the graph is $50$-partite.

Hint 2:

Each partite set contains exactly two elements.

Full Solution:

For colors $c_1,\dotsc,c_{50}$, assign color $c_i$ to numbers $2i-1$ and $2i$. Note that no two consecutive numbers can have a common divisor other than $1$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Very smart. Thank you $\endgroup$
    – Ibrakhim Tolobekov
    Jun 9 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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