1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ I think you should post your code/trial. In that case, others maybe help you by runing and editing your code. $\endgroup$ – xyz Oct 24 '15 at 5:58
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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]

enter image description here

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ yes, I mean great circles on a sphere. I defined my graph and when I use the ChromaticPolynomial command it returns that: ChromaticPolynomial[ PlanarGraphPL[{{0, {{-19.7169, 3.80447}, {-36.8575, 8.29989}, {-53.6898, 13.8393}, {-70.1502, 20.4017}, {-86.1766, 27.9625}, {-101.709, 36.493}, {-116.687, 45.9611}, {-131.057, 56.3311}, {-144.762, 67.5637}, {-157.752, 79.6167}, {-169.977, 0.133376}, {73.0254, -2.13778}, {55.3449, -3.32558}, {37.6249, \ -3.42554}, {19.9321, -2.4373}}}, {0, 0}}, {{-1.97567, 0.311021}, {1.97567, -0.311021}}], k] $\endgroup$ – user35019 Oct 23 '15 at 22:22
  • $\begingroup$ For cyclic graphs there might be something usable at this Demonstration $\endgroup$ – Daniel Lichtblau Oct 23 '15 at 22:25
  • $\begingroup$ @Iris What is PlanarGraphPL? Your graph should consists solely of a list of vertexes and edges. The spatial locations of the vertexes are irrelevant to the graph structure, and hence to the chromatic number. $\endgroup$ – David G. Stork Oct 23 '15 at 22:27
  • $\begingroup$ Well, I am using the code from "Mathematica in action, Stan Wagon, Chapter 17 - Great Circle" in order to generate the circles on a sphere. This code has some extra codes and PlanarGraphPL is one of them my code to generate the graph is : {g, g3D} = RandomGreatCircleGraph[2, Include3DPlot -> True, PlotStyle -> {Opacity[0.5], Yellow}]; $\endgroup$ – user35019 Oct 23 '15 at 22:49
  • $\begingroup$ @Iris, that doesn't output a Graph[] object, which is needed by ChromaticPolynomial[]. $\endgroup$ – J. M. will be back soon Oct 23 '15 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy