{"id":83,"date":"2010-07-13T16:12:46","date_gmt":"2010-07-13T16:12:46","guid":{"rendered":"http:\/\/mathriddles.williams.edu\/?p=83"},"modified":"2025-01-27T09:41:32","modified_gmt":"2025-01-27T14:41:32","slug":"primeary-colors","status":"publish","type":"post","link":"https:\/\/sites.williams.edu\/mathriddles\/difficulty\/medium\/primeary-colors\/","title":{"rendered":"PRIMEary Colors"},"content":{"rendered":"<p>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:<\/p>\n<ol>\n<li>The vertices are the integers 2, 3, 4, 5, 6, &#8230;., 9,998, 9,999, and 10,000<\/li>\n<li>Two vertices are connected by an edge if they share a common factor. So there isn&#8217;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, &#8230;<\/li>\n<\/ol>\n<p>Prove that the coloring number of this graph is at least 13.<\/p>\n<p>Problem created by Steven Miller as a practice test question for Princeton&#8217;s Discrete Math 341, Fall &#8217;98.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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: The vertices are the integers 2, 3, 4, 5, 6, &#8230;., 9,998, 9,999, and 10,000 Two vertices&hellip;<\/p>\n","protected":false},"author":2861,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[12,7,18],"tags":[],"class_list":["post-83","post","type-post","status-publish","format-standard","hentry","category-combinatorics","category-medium","category-number-theory"],"acf":[],"_links":{"self":[{"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/posts\/83","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/users\/2861"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/comments?post=83"}],"version-history":[{"count":1,"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/posts\/83\/revisions"}],"predecessor-version":[{"id":1177,"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/posts\/83\/revisions\/1177"}],"wp:attachment":[{"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/media?parent=83"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/categories?post=83"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sites.williams.edu\/mathriddles\/wp-json\/wp\/v2\/tags?post=83"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}