Graph Coloring

• Let be graph. The graph is -colorable if it is possible to assign for each vertex colors such that adjacent vertices have different colors.
• A graph is -edge colorable if its edges can be colored with colors so that no two adjacent edges (i.e., edges that share an endpoint) have the same color .
• A map is -face colorable if its faces can be colored with colors such that no two faces with a boundary edge in common have the same color.

Chromatic Number §

• The chromatic number of denoted implies that is -colorable but not -colorable.

• A graph has a chromatic index denoted if it is -edge colorable but not edge colorable.

• (Wilson Ch. 18) Brook’s Theorem - If is a simple connected graph and not an odd cycle, and if , then is -colorable.

• Vizing’s Theorem ¹

• (Wilson 20.2)

• (Wilson 20.4) Konig’s Theorem If is bipartite, then

Four Color Theorem §

• Vertex Formulation: Every simple planar graph is -colorable.
• Face Formulation: Any map is -face colorable
• (Wilson 20.3) Edge Formulation: for each cubic map of .

Chromatic Polynomials §

• Let be a simple graph. The chromatic polynomial, denoted is the number of ways to perform a vertex coloring with colors available.

  • If

• (Aydelotte 2.6, Wilson 21.2). The chromatic polynomial is a polynomial.

• The Deletion-Contraction Formula. If is a simple ² graph, then

• (Aydelotte 2.4) Let be a simple graph, be a decomposition of . Then

• (Aydelotte 3.1) The degree of l is the number of vertices of .

• (Aydelotte 3.2) The chromatic polynomial has the following properties.

  1. The Leading Coefficient of is .
  2. The absolute value of the coefficient of the term in is the number of edges of .
  3. The first coefficient of is positive, and all terms alternate in sign.
  4. All coefficients are integer.
  5. If the coefficient of , then so is .

• (Aydelotte 3.2) The constant term of the chromatic polynomial of any graph is .

• (Aydelotte 3.7) The chromatic polynomial of is

• (Aydelotte 3.8) The chromatic polynomial of

• (Theorem) The chromatic polynomial of a tree of vertices is

• Read’s Theorem For a given chromatic polynomial with coefficients , is unimodal. That is, there is some such that

Chromatic Equivalence §

• Two undirected graphs are said to be chromatically equivalent if they have the same chromatic polynomial but they are not isomorphic.

• An undirected graph is chromatically unique if for any graph with the same chromatic polynomial as , then

• An undirected graph is a -critical if and the vertex deletion of any vertex yields a graph with a smaller chromatic number, namely for vertex we have

• (Wilson e17.11.3a) Let be -critical. Then [

• (Wilson e17.11.3b) Let be a -critical graph. Then does not contain cut vertices. A special case of Wilson e17.11.3b. ³

• (Wilson e17.11z) Let be a -critical graph. Any vertex cut of cannot be in a clique.
  • This follows from Wilson e17.11.3b except applying the argument to multiple vertices instead.

Links §

• An Exploration of the Chromatic Polynomial by Aydelotte

• Fundamental Constructs of Graph Theory

• Families of Graphs

Footnotes §

1. This follows by coloring a vertex one color, and all its neighbors any of the remaining colors (at most ) by definition. ↩

2. Consider . The number of colorings in where and have different colors is . The number of colorings where and have the same colors is where is contracted and . ↩

3. Let consist of components by virtue of beng a cut-set. Now, is colorable. Any component combined with (and the edges to ) is colorable. Taking the union of the components gives us a coloring. ↩