PRIMEary Colors

We define the coloring number of a graph of V vertices and E edges to be the smallest number of colors such that no two vertices that share an edge are colored the same. Consider the following graph:

  1. The vertices are the integers 2, 3, 4, 5, 6, …., 9,998, 9,999, and 10,000
  2. Two vertices are connected by an edge if they share a common factor. So there isn’t an edge between 2 and 3, but there is between 2 and 6, another between 3 and 6, but none between 2 and 5, between 3 and 5, …

Prove that the coloring number of this graph is at least 13.

Problem created by Steven Miller as a practice test question for Princeton’s Discrete Math 341, Fall ’98.

9 Comments

  1. Steven Miller on September 6, 2012 at 12:55 pm

    Sergio: please email me directly as I don’t want to post solns (but yes, you are right here): sjm1 AT williams.edu



  2. Steven Miller on March 15, 2012 at 1:12 am

    To the poster who wrote: “Hi, I think you should say that two vertices are connected by an edge …” I don’t want to say that for a certain reason. What you wrote after is correct. Email me if you want to chat further (sjm1 AT williams.edu).



  3. Marco on March 14, 2012 at 9:12 pm

    Hi, I think you should say that two vertices are connected by an edge if one divides the other (and indeed you can prove that the coloring number is >= 13 in this case).
    Otherwise, as it is stated now, all the even numbers share the common factor 2, so they are all connected to each other, and you need at least 5,000 different colors.



  4. Steven Miller on December 30, 2011 at 9:36 pm

    Sure: I believe it’s WordPress (http://wordpress.com/); I’ll check with some of the OIT people at Williams and email you.



  5. Homestay for Student on December 30, 2011 at 8:02 pm

    Hi would you mind sharing which blog platform you’re using? I’m looking to start my own blog soon but I’m having a difficult time choosing between BlogEngine/Wordpress/B2evolution and Drupal. The reason I ask is because your design seems different then most blogs and I’m looking for something completely unique. P.S My apologies for being off-topic but I had to ask!



  6. Steven Miller on September 6, 2011 at 2:13 am

    Glad you’re enjoying the page.



  7. Mariella Mcginity on September 4, 2011 at 5:11 pm

    Utterly composed topic material , thanks for selective data .



  8. Steven Miller on July 26, 2011 at 6:48 pm

    The riddle specifically excludes 1 from the graph



  9. pi on July 26, 2011 at 5:25 pm

    Wouldn’t the coloring number have to be 9,999 since all the vertices are connected? Every integer shares the common factor of 1.



Leave a Comment