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?

$\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_
    Commented Jun 9, 2023 at 16:29
  • $\begingroup$ HOW? Number of even numbers are 50 not 51 $\endgroup$ Commented Jun 9, 2023 at 16:33
  • $\begingroup$ In addition to the 25 prime numbers, there are 4 other isolated vertices: 1, 49, 77, 91. $\endgroup$
    – Stef
    Commented Jun 9, 2023 at 21:33

1 Answer 1

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

$\endgroup$
1
  • 1
    $\begingroup$ Very smart. Thank you $\endgroup$ Commented Jun 9, 2023 at 17:23

Your Answer

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

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