Graph Coloring

This picture illustrates one area of a rather young branch of mathematics called graph theory. A graph is a collection of vertices (dots) and edges (lines) which connect the vertices. One portion of graph theory deals with coloring the vertices of a graph so that adjacent (joined) vertices are not colored the same. This particular graph can be vertex colored using only five colors. Many applications arise from graph coloring.

This graph is one of an infinite family of graphs which confirms a conjecture of G.A.Dirac from 1970. He conjectured that there exist vertex k-critical graphs containing no critical edge for k > 4. The family = cir(, ), r,s > 2, confirms the conjecture for all positive integers k such that k-1 is not prime. Here, the vertices of are labelled by the members of , the least residues modulo n = 4rs + 1 and the generating set for this circulant graph is

The graph illustrated is the graph G_2,2 which is a 5-chromatic vertex critical graph containing no critical edges.

Contributed by John Lattanzio.

| prev | index | next |

The image along the right side of this page is chosen at random from the graphics gallery. Visit the graphics gallery to see all of the images and their descriptions.

Correspondence regarding this site should be sent to its maintainer, H. Edward Donley, <hedonley@iup.edu>. Please see IUP's statement regarding pages that do not officially represent the university.