Chromatic Roots of Cubic Graphs

Locating the chromatic roots of graphs is an interesting mostly open problem, although progress has been made on it recently, including the resolution of some significant open questions.

I have written an interactive visualization tool for exploring the chromatic roots of cubic graphs at your own leisure. Go to the page Cubic Chromatic Roots to experiment with this.

If you are merely interested in finding the extremal values that can be taken by cubic chromatic roots, then the following table lists the graphs with the maximum values for the modulus of chromatic roots, size of the largest real root, size of largest real part of chromatic roots and the size of the largest imaginary part.

Clicking on the value will get you a listing of the edges of the graph in an obvious format.

As I am too lazy to write a proper graph drawing routine, the next best thing is to provide a simple interface to the GeomNet Graph Drawing Server.

Some Immediate Observations and Conjectures

Modulus

The two graphs with the maximum moduli of chromatic roots are the complete graph K₄ with a value of 3, and the complete bipartite graph K_3,3 with a value of 2.897441. For other k-regular graphs, computation seems to suggest that K_k,k has the largest modulus for k>3. The 20 vertex graph that comes close with 2.856887 is a vertex transitive generalized Petersen graph where the inner cycle has connection set {-3,3}. (In other words take n=10 and k=3 in the following description from Mathworld. )

• Conjecture:

  For k>3 the k-regular graph with the largest modulus of a chromatic root is K_k,k.

• Conjecture:

  For k=3 the k-regular graph with the largest modulus of a chromatic root is K₄. The graph K_3,3 has the second largest modulus.

• Conjecture:

  The previous two conjectures hold if k-regular is replaced by maximum degree k, and possibly even 2nd largest degree k.

Real Root

The graphs with the largest real roots are the graph on 12 vertices obtained by stringing together a three K₄-e into a cycle, and the analogous graph on 20 vertices using five K₄-e. These graphs are uniquely the graphs with the largest number of triangles (6 and 10 respectively) on 12 and 20 vertices. As the number of triangles increases, the root plots appear to become more elliptical, as though the imaginary parts are "squeezed down", forcing the real parts to the left and right.

This picture shows the roots of the cubic graphs on 20 vertices with 0 triangles (red), 5 triangles (green) and 10 triangles (blue, but only 1 graph) respectively.

• Conjecture:

  The 12-vertex graph noted above has the largest real chromatic root of any cubic graph (resp. graph of max degree 3, resp. graph of 2nd max degree 3).

Real Part

This seems to be dominated by the maximum real root as soon as we hit 12 vertices and onwards.

Imaginary Part

The cubic graph on up to 20 vertices with the largest imaginary part of a chromatic root is our old friend the Petersen graph. The next largest is a graph on 20 vertices, which turns out to be 2 Petersen graphs, each with an edge deleted and then the four vertices of degree 2 connected back together. The Petersen graph is probably the cubic graph with the largest imaginary part of a root.