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
4
$\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.

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.

$\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