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?
-
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
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.
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]
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]
.
-
$\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 byChromaticPolynomial[]
. $\endgroup$ – J. M. will be back soon♦ Oct 23 '15 at 22:54