Chromatic number for “great circle” graph

Question

I would like to calculate the chromatic number for a great circle graph. I tried this example in this link. I first tried to calculate the chromatic number for PetersenGraph as in the example but Mathematica did not give me the same result. I saw another example in this link. It worked for the example, but when I applied it to my great circle graph it did not work. Is there some special functions for great circle graphs?

Answer 1

For calculating the chromatic number of any graph, you can simply do the following:

ChromaticNumber[g_] := MinValue[{z, z > 0 && ChromaticPolynomial[g, z] > 0}, z, Integers];

That is, the above finds the smallest integer such that the input graph has at least one proper coloring.

Do note, however, that this method should be very slow and practically unusable for anything but small graphs. If your graphs are a little larger and/or harder to color, it's a better idea to try e.g., IGraphM.

Answer 2

IGraph/M includes several functions for colouring. See the Graph Colouring sections of its documentation.

To compute the chromatic number, use IGChromaticNumber.

g = PetersenGraph[];

IGChromaticNumber[g]
(* 3 *)

We can also produce an actual colouring.

Graph[g, VertexSize -> Large, GraphStyle -> "BasicBlack"] // 
 IGVertexMap[ColorData[101], VertexStyle -> IGMinimumVertexColoring]

Answer 3

I presume by "great circle graph" you mean a CycleGraph.

Note that:

ChromaticPolynomial[g,k] gives the number of vertex colorings of g with k colors.

i = 4;
k = 2;
ChromaticPolynomial[CycleGraph[i], k]

2

i = 10;
k = 4;
ChromaticPolynomial[CycleGraph[i], k]

59052

If instead you mean the graph defined by the intersection points of great circles on a sphere, then you must define your graph first, then compute ChromaticPolynomial[g,k].