{"id":453,"date":"2007-06-26T15:48:04","date_gmt":"2007-06-26T15:48:04","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/06\/26\/get-out-your-crayons-its-graph-coloring-time\/"},"modified":"2007-06-26T15:48:04","modified_gmt":"2007-06-26T15:48:04","slug":"get-out-your-crayons-its-graph-coloring-time","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/06\/26\/get-out-your-crayons-its-graph-coloring-time\/","title":{"rendered":"Get out your crayons: it's graph coloring time!"},"content":{"rendered":"

One kind of graph problem that’s extremely widely used in computer science is called graph coloring<\/em>. There’s two versions of it, *vertex coloring*, and *face coloring*.
\nVertex coloring is the one that’s more widely used. Edge coloring problems are all variations on the following: given a graph *G=(V,E)*, find a mapping of colors to vertices, such than if two vertices are adjacent, they’re assigned different colors?
\nThe variants of the vertex coloring problem are things like:
\n* What’s the *minimum* number of colors (aka the *chromatic number* of the graph)
\nthat can be used to color a graph?
\n* Given an integer N, can you find an N-coloring of the graph?
\nThe face coloring problem is more complicated to describe. Suppose you have a *planar* graph. (Remember that that means a graph which can be drawn on a plane with no edges crossing.) Suppose further that the graph has the property that from any vertex v, there is a path through the graph from v to v. Then that graph is called a *map*. For a map drawn on a plane, every edge is part of at least one cycle. The smallest possible cycles – that is, the cycles which are not bisected by any other edges of the graph – are called *countries* or *faces* of the graph. The face coloring problem assigns colors to the *faces* of a graph, so that no two faces that share an edge are the same color. There’s an extremely fascinating proof that any planar map can be face-colored with no more than four colors. We’ll talk about later – it’s the first computer assisted proof that I’m aware of.<\/p>\n


\nBut for now, back to vertex coloring. How can we find the chromatic number of an arbitrary graph, G (also written χ(G))?
\n\"2color.jpg\"
\nThe one that students often come up with as a first guess – is to find the vertex with highest degree, and that the degree of that vertex will be one smaller than the chromatic number. Alas, it’s not so easy. Take a look at the graph to the right: the maximum degree of a vertex is 4, but it can be 2-colored.
\n\"notmaxdegree.jpg\"
\nAnother common idea is that the chromatic number should be the size of the smallest clique in the graph. Again, no dice – look at the example to the right: the largest clique has degree four, but the graph needs 5 colors. But the largest clique *is* a lower bound.
\nWhat we end up with isn’t particularly pretty. There’s no simple way of finding the minimum coloring of a graph. What there *is* is a method of figuring it out from pieces using the lowering bound provided by the the largest clique. It’s based on the idea of a *critical subgraph*.
\nA critical subgraph C of a graph G is a *proper* subgraph of G – that is, a subgraph of G where C≠G – such that for every proper subgraph B of C, χ(B)<&chi(C). So we can *reduce* G to its largest critical subgraph – and the chromatic number of that subgraph is the same as the chromatic number of G.
\nSo we’ve reduced the problem to identifying the largest critical subgraph. There are a couple of useful properties that can help us:
\n1. Critical subgraphs are always connected. This should be pretty obvious – if the graph
\nisn’t connected, then you can color the disconnected subgraphs separately, which
\nwould mean that it’s not critical.
\n2. In a critical subgraph C with chromatic number χ(C), every node
\nwill have minimum degree χ(C)-1.
\nBut aside from those, we’re mostly on our own. And just to be spiteful, graph colorings also have a nasty property.
\nSuppose you have a graph G. The number of edges in the smallest cycle in G is called the *girth* of G.
\nFor any x,y≥2, there is a graph with girth x, and chromatic number y. What that means is that you can’t do things like rely on cliques, even as an approximation. Because, for example, a graph with chromatic number 300 isn’t even guaranteed to contain any cliques of size three! Because a 3-clique is a triangle, which is a cycle of size 3… But there are graphs with chromatic number 300, and girth 50.
\n\"groltzsch.jpg\"
\nJust for an example of a graph with this kind of property: the figure to the right is called the Grötzcsh graph. It’s got girth four, but it contains no triangles at all. Try and figure out how many colors it needs.<\/p>\n","protected":false},"excerpt":{"rendered":"

One kind of graph problem that’s extremely widely used in computer science is called graph coloring. There’s two versions of it, *vertex coloring*, and *face coloring*. Vertex coloring is the one that’s more widely used. Edge coloring problems are all variations on the following: given a graph *G=(V,E)*, find a mapping of colors to vertices, […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[25],"tags":[],"class_list":["post-453","post","type-post","status-publish","format-standard","hentry","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-7j","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/453","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=453"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/453\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=453"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=453"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=453"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}