GRAPH COLORING CHALLENGE

Your challenge, should you choose to accept it, is to answer as many of the following questions as completely as you can before the end of the hour. You may use any of the resources in the room, including your projects and writeups, the computer, and fellow students. GOOD LUCK.

First, take 10 minutes to read through the questions with your partner and decide which ones are easy and which ones you already have answers for.

PROCEDURE: For each problem, one student will read the problem to the class, writing relevant details on the board. The entire class must come to consensus on an appropriate answer before work begins on another problem. (You don't have to do them in the order given.)

1.

What is the chromatic polynomial for an n-path?

2.

The minimum number of colors needed to properly color a graph is called the ``chromatic number.'' What is the chromatic number for the empty graph on n vertices? ...for a complete graph? ...for an n-path? ...for an n-cycle?

3.

The ``degree'' of a vertex is the number of edges connected to that vertex. A ``regular'' graph is one in which every vertex has the same degree. Sketch some examples of 1-regular graphs (graphs in which every vertex has degree 1). Can you describe all possible 1-regular graphs on n vertices? What about 2-regular graphs?

4.

(a)

What is the chromatic polynomial for a 3-cycle?

(b)

What is the chromatic polynomial for a 4-cycle?

(c)

Can you find a recursive definition for the chromatic polynomial of an n-cycle? (i.e., Can you find a formula for the chromatic polynomial of an n-cycle in terms of the chromatic polynomial of an (n-1)-cycle?)

5.

Consider the chromatic polynomial P(G,x) of a graph G with n vertices and chromatic number k.

(a)

Can P(G,x) have a constant term? Why not?

(b)

What is the largest possible value for the degree of P? (What is the smallest possible value for the degree of P?)

(c)

What is the leading coefficient of P?

(d)

How is the chromatic number related to the chromatic polynomial in factored form?

6.

Compare many tables of coefficients from chromatic polynomials of many types of graphs. What characteristics do they ALL have in common? Can you explain why these characteristics must always appear? Can you prove it?

7.

A ``bipartite graph'' B has two disjoint sets of vertices, V<sub>1</sub> and V<sub>2</sub>, with the property that each edge in B has one vertex in V<sub>1</sub> and one vertex in V<sub>2</sub>. A ``complete'' bipartite graph is a bipartite graph in which EVERY vertex in V₁ is connected by an edge to EVERY vertex in V₂.

(a)

Let `` B[m<sub>1</sub>,m<sub>2</sub>]'' denote the complete bipartite graph with m<sub>1</sub> vertices in V<sub>1</sub> and m<sub>2</sub> vertices in V<sub>2</sub>. Find the chromatic polynomials (in terms of m<sub>2</sub>) for the two cases m<sub>1</sub>=1 and m<sub>1</sub>=2. Can you find a general formula for the chromatic polynomial of B[m<sub>1</sub>,m<sub>2</sub>] or determine its chromatic number? (In Mathematica, B[m<sub>1</sub>,m<sub>2</sub>] is called ``CompleteGraph[m₁,m₂]''.)

(b)

Invent a reasonable definition of ``tripartite'' and find a formula for the chromatic polynomial of a complete tripartite graph.

(c)

Suppose you have a bipartite graph which is not necessarily complete. What can you say about its characteristic polynomial and chromatic number (if anything)?

Needless to say, I am not so much interested in the actual answers to the questions. I am more interested in your methods of investigation and your justification of your answers/conjectures.