Tag Archives: papers

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]. Continue reading

Leave a comment

Filed under numbers