patternMinor
Let the vertices of the graph G be the numbers 1, 2, ..., 100, a. Determine χ(G), the chromatic number of the graph G
Viewed 0 times
thenumbergraphnumberschromatic100letdeterminevertices
Problem
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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#160599, answer score: 5
Revisions (0)
No revisions yet.