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.

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].