Bounding Chi: Cliques and Suboptimal Coloring (or, Why My Mom Took Away My Crayons)

My first experience with suboptimal coloring was when I was about two years old.  My mom got me one of those books with blank pictures of cartoon characters and I just scribbled all over the pages with red crayon.  That’s pretty much what my latest paper is about.  Here’s a PDF. The introduction is below, and continues after the jump.  Some stuff in the paper is probably wrong, so let me know if you catch any mistakes.

Computational Methods for Bounding Chromatic Numbers of Graphs

1 Introduction
Many central problems in graph theory involve the process of graph coloring. A coloring of a graph is an assignment of a label, or “color,” to each vertex, such that no two connected vertices have the same color. Perhaps the most famous example is the problem of map coloring: a map determines a graph by assigning a node to each country, with an edge between two nodes whenever the corresponding countries share a border. A coloring of the graph then corresponds to a coloring of the map in which neighboring countries never share a color. Appel and Haken famously proved that for maps, there is always a coloring with no more than four colors [1].

In fact, for any graph G, there is a minimum number of colors needed to color G. This number is denoted χ(G) and is called the chromatic number of G. There are known bounds on the chromatic numbers of certain classes of graphs. For instance, Appel and Haken’s result is the statement that if G represents a map (a so-called planar graph), then χ(G) ≤ 4. However, for a general arbitrary graph, the only known way to calculate χ(G) exactly is to find an optimal coloring, and the only known algorithm for optimal coloring is to enumerate every possible coloring of the graph and find a best one. That process is immensely computationally intensive; for an n-vertex graph, enumerating all colorings requires up to O(n^(n+2)) steps! It is therefore highly impractical, in many cases, to find the exact value of χ(G), and so we turn to approximations.

In this paper, we will explore a few computational methods for placing upper and lower bounds on χ(G) for random graphs without attempting to calculate it exactly. If we can find a coloring of G that uses n colors (an n-coloring) then we know that χ(G) ≤ n. To this end, we will explore two methods for coloring graphs in ways that do not necessarily use the smallest possible number of colors: the greedy coloring algorithm, which runs in at most O(n^2) steps; and the method of independent sets, which gives better results but can require up to O(n2^n) steps. We can also put a lower bound on χ(G) by finding cliques, or complete subgraphs, of G. χ(G) must be at least as large as the size of the largest clique in G, since no two vertices in a clique can share a color. Finding the size of the largest clique in G takes at most O(2^n) steps.

We will test the effectiveness of these algorithms on samples from two families of graphs. We will primarily use graphs from G (n, p), the space of random undirected graphs of order n, where the probability that there will be an edge between any pair of nodes is p. The second family of graphs that we will use is Gk (n, p), the space of random undirected graphs of order n such that there is never an edge between vertices vi and vj if i ≡ j (mod k), and the probability that there is an edge between any other pair of vertices is p.

In the following section, we will discuss the greedy coloring algorithm. We will then address the problem of finding cliques in a graph, after which we will use the same clique-finding algorithm to derive the independent-sets coloring algorithm. Finally, we will derive the complexities of the algorithms used in this paper.


Leave a comment

Filed under numbers

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s