Colourings
==========

.. _graph-colouring:



The functions given here are not applicable to digraphs.

.. magma:function:: ChromaticNumber(G) 
   :input_types: GrphUnd
   :output_types: RngIntElt
   :label: ChromaticNumber_Grph
   
   The chromatic number of the graph :math:`G`, that is, the minimum number of 
   colours required to colour the vertices of :math:`G` such that no two adjacent 
   vertices share the same colour.

.. magma:function:: OptimalVertexColouring(G)
   :input_types: GrphUnd
   :output_types: SeqEnum
   :label: OptimalVertxColouring_Grph

   An  optimal vertex colouring of the graph :math:`G` as a sequence of sets of 
   vertices of :math:`G`. Each set in the sequence contains the vertices which are 
   given the same colour. Some optimal vertex colouring is returned, others may 
   exist.

.. magma:function:: ChromaticIndex(G)
   :input_types: GrphUnd
   :output_types: RngIntElt
   :label: ChromaticIndex_Grph

   The chromatic index of the graph :math:`G`, that is, the minimum number of 
   colours required to colour the edges of :math:`G` such that no two adjacent 
   edges share the same colour.

.. magma:function:: OptimalEdgeColouring(G)
   :input_types: GrphUnd
   :output_types: SeqEnum
   :label: OptimalEdgeColouring_Grph

   An  optimal edge colouring of the graph :math:`G` as a sequence of sets of edges 
   of :math:`G`. Each set in the sequence contains  the edges which are given the 
   same colour. Some optimal edge colouring is returned, others may exist.

.. magma:function:: ChromaticPolynomial(G)
   :input_types: GrphUnd
   :output_types: RngUPolElt
   :label: ChromaticPolynomial_GrphUnd

   The chromatic polynomial of the graph :math:`G`. For a given natural number :math:`x`, 
   the chromatic polynomial :math:`p_{G}(x)` gives the number of colourings of :math:`G` 
   with  colours :math:`1, 2, \ldots, x`.

 

.. magma:example:: Example: Chromatic Number
   :label: ChromaticNumber-example

   We illustrate the use of these functions with the following graph:

   .. code-block:: magma

        > G:=Graph< 5 | [{2,5}, {1,3,5}, {2,4,5}, {3,5}, {1,2,3,4} ]>;
        > ChromaticNumber(G);
        3
        %%a> assert $1 eq 3;
        > OptimalVertexColouring(G);
        [
        { 1, 3 },
        { 2, 4 },
        { 5 }
        ]
        > ChromaticIndex(G);
        4
        %%a> assert $1 eq 4;
        > OptimalEdgeColouring(G);
        [
        { {1, 2}, {3, 5} },
        { {2, 3}, {1, 5} },
        { {3, 4}, {2, 5} },
        { {4, 5} }
        ]
        > ChromaticPolynomial(G);
        $.1^5 - 7*$.1^4 + 18*$.1^3 - 20*$.1^2 + 8*$.1