- VertexColouring
- MinimumVertexColouring
- ChromaticNumber
- CompleteSubgraphs
- CompleteSubgraphsOfGivenSize
- MaximumClique
- CliqueNumber

The following sections describe functions for (proper) vertex-colouring and determining complete subgraphs of a given simple graph. Included are functions for determining the chromatic number and the clique number of a simple graph.

The function `CompleteSubgraphsOfGivenSize`

can be used to determine
the complete subgraphs with given vertex-weight sum in a vertex-weighted
graph indexvertex-weighted graph, where the weights can be positive
integers or non-zero vectors of non-negative integers.

`VertexColouring( `

` )`

`VertexColouring( `

`, `

` )`

`VertexColouring( `

`, `

`, `

` )`

This function returns a proper vertex-colouring `C` for the graph
`gamma`, which must be simple. A **proper vertex-colouring** indexproper
vertex-colouring of `gamma` is an assignment of colours to the vertices
of `gamma`, such that, if [*i*,*j*] is an edge, then vertices *i* and *j*
are assigned different colours.

The returned proper vertex-colouring `C` is given as a list of positive
integers (the **colours**), indexed by the vertices of `gamma`, with the
property that *C* [*i*] ≠ *C* [*j*] whenever [*i*,*j*] is an edge of `gamma`.

If the optional parameter `k` is given, then `k` must be a non-negative
integer. In this case, a proper vertex-colouring using at most `k`
colours is returned, if such a colouring exists, and `fail`

otherwise.

If, in addition to `k`, the optional parameter `m` is given, then `m`
must be a a non-negative integer, such that there is no monochromatic
set of vertices of size greater than `m` in any proper vertex-colouring
of `gamma` which uses at most `k` colours. This information (which is
not checked) may help to speed up the function.

gap> J:=JohnsonGraph(5,2); rec( adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ], group := Group([ (1,5,8,10,4) (2,6,9,3,7), (2,5)(3,6)(4,7) ]), isGraph := true, isSimple := true, names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], order := 10, representatives := [ 1 ], schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1 ] ) gap> VertexColouring(J); [ 1, 3, 5, 4, 2, 3, 6, 1, 5, 2 ] gap> VertexColouring(J,5); [ 1, 2, 3, 4, 5, 4, 2, 1, 3, 5 ] gap> VertexColouring(J,4); fail

`MinimumVertexColouring( `

` )`

This function returns a minimum vertex-colouring `C` for the graph
`gamma`, which must be simple. A **minimum vertex-colouring** indexminimum
vertex-colouring is a proper vertex-colouring using as few colours
as possible.

The returned minimum vertex-colouring `C` is given as a list of positive
integers (the **colours**), indexed by the vertices of `gamma`, with the
property that *C* [*i*] ≠ *C* [*j*] whenever [*i*,*j*] is an edge of `gamma`,
and subject to this property, the number of distinct elements of `C`
is as small as possible.

See also VertexColouring.

gap> J:=JohnsonGraph(5,2); rec( adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ], group := Group([ (1,5,8,10,4) (2,6,9,3,7), (2,5)(3,6)(4,7) ]), isGraph := true, isSimple := true, names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], order := 10, representatives := [ 1 ], schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1 ] ) gap> MinimumVertexColouring(J); [ 1, 2, 3, 4, 5, 4, 2, 1, 3, 5 ]

`ChromaticNumber( `

` )`

This function returns the chromatic number of the given graph `gamma`,
which must be simple. The **chromatic number** indexchromatic number of
`gamma` is the minimum number of colours needed to properly vertex-colour
`gamma`, that is, the number of colours used in a minimum vertex-colouring
of `gamma`.

See also MinimumVertexColouring.

gap> ChromaticNumber(JohnsonGraph(5,2)); 5 gap> ChromaticNumber(JohnsonGraph(6,2)); 5 gap> ChromaticNumber(JohnsonGraph(7,2)); 7

`CompleteSubgraphs( `

` )`

`CompleteSubgraphs( `

`, `

` )`

`CompleteSubgraphs( `

`, `

`, `

` )`

Let `gamma` be a simple graph and `k` an integer. This function returns
a set `K` of complete subgraphs of `gamma`, where a complete subgraph is
represented by its vertex-set. If `k` is non-negative then the elements
of `K` each have size `k`, otherwise the elements of `K` represent maximal
complete subgraphs of `gamma`. (A **maximal complete subgraph** of `gamma`
is a complete subgraph of `gamma` which is not properly contained in
another complete subgraph of `gamma`.) The default for `k` is −1,
i.e. maximal complete subgraphs. See also `CompleteSubgraphsOfGivenSize`

,
which can be used to compute the maximal complete subgraphs of given
size, and can also be used to determine the (maximal or otherwise)
complete subgraphs with given vertex-weight sum in a vertex-weighted
graph.

The optional parameter `alls` controls how many complete subgraphs are
returned. The valid values for `alls` are 0, 1 (the default), and 2.

**Warning:** Using the default value of 1 for `alls` (see below) means that
more than one element may be returned for some `gamma``.group`

orbit(s)
of the required complete subgraphs. To obtain just one element from each
`gamma``.group`

orbit of the required complete subgraphs, you must give
the value 2 to the parameter `alls`.

If `alls`=0 (or `false`

for backward compatibility) then `K` will contain
at most one element. In this case, if `k` is negative then `K` will
contain just one maximal complete subgraph, and if `k` is non-negative
then `K` will contain a complete subgraph of size `k` if and only if
such a subgraph is contained in `gamma`.

If `alls`=1 (or `true`

for backward compatibility) then `K` will contain
(perhaps properly) a set of `gamma``.group`

orbit-representatives of
the maximal (if `k` is negative) or size `k` (if `k` is non-negative)
complete subgraphs of `gamma`.

If `alls`=2 then `K` will be a set of `gamma``.group`

orbit-representatives of the maximal (if `k` is negative) or size `k`
(if `k` is non-negative) complete subgraphs of `gamma`. This option
can be more costly than when `alls`=1.

Before applying `CompleteSubgraphs`

, one may want to associate the full
automorphism group of `gamma` with `gamma`, via `gamma````
:=
NewGroupGraph( AutGroupGraph(
```

`gamma``), `

`gamma`` );`

.

An alternative name for this function is `Cliques`

indexCliques.

See also CompleteSubgraphsOfGivenSize.

gap> gamma := JohnsonGraph(5,2); rec( isGraph := true, order := 10, group := Group([ ( 1, 5, 8,10, 4)( 2, 6, 9, 3, 7), ( 2, 5)( 3, 6)( 4, 7) ]), schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1 ], adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ], representatives := [ 1 ], names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], isSimple := true ) gap> CompleteSubgraphs(gamma); [ [ 1, 2, 3, 4 ], [ 1, 2, 5 ] ] gap> CompleteSubgraphs(gamma,3,2); [ [ 1, 2, 3 ], [ 1, 2, 5 ] ] gap> CompleteSubgraphs(gamma,-1,0); [ [ 1, 2, 5 ] ]

`CompleteSubgraphsOfGivenSize( `

`, `

` )`

`CompleteSubgraphsOfGivenSize( `

`, `

`, `

` )`

`CompleteSubgraphsOfGivenSize( `

`, `

`, `

`, `

` )`

`CompleteSubgraphsOfGivenSize( `

`, `

`, `

`, `

`, `

` )`

`CompleteSubgraphsOfGivenSize( `

`, `

`, `

`, `

`, `

`, `

` )`

Let `gamma` be a simple graph, and `k` a non-negative integer or vector
of non-negative integers. This function returns a set `K` (possibly
empty) of complete subgraphs of size `k` of `gamma`. The vertices may
have weights, which should be non-zero integers if `k` is an integer and
non-zero *d*-vectors of non-negative integers if `k` is a *d*-vector,
and in these cases, a complete subgraph of **size** `k` means a complete
subgraph whose vertex-weights sum to `k`. The exact nature of the set
`K` depends on the values of the parameters supplied to this function. A
complete subgraph is represented by its vertex-set.

The optional parameter `alls` controls how many complete subgraphs are
returned. The valid values for `alls` are 0, 1 (the default), and 2.

**Warning:** Using the default value of 1 for `alls` (see below) means that
more than one element may be returned for some `gamma``.group`

orbit(s)
of the required complete subgraphs. To obtain just one element from each
`gamma``.group`

orbit of the required complete subgraphs, you must give
the value 2 to the parameter `alls`.

If `alls`=0 (or `false`

for backward compatibility) then `K` will
contain at most one element. If `maxi`=`false`

then `K` will contain one
element if and only if `gamma` contains a complete subgraph of size `k`.
If `maxi`=`true`

then `K` will contain one element if and only if `gamma`
contains a maximal complete subgraph of size `k`, in which case `K`
will contain (the vertex-set of) such a maximal complete subgraph.
(A **maximal complete subgraph** of `gamma` is a complete subgraph of
`gamma` which is not properly contained in another complete subgraph
of `gamma`.)

If `alls`=1 (or `true`

for backward compatibility) and `maxi`=`false`

,
then `K` will contain (perhaps properly) a set of `gamma``.group`

orbit-representatives of the size `k` complete subgraphs of `gamma`.
If `alls`=1 (the default) and `maxi`=`true`

, then `K` will contain
(perhaps properly) a set of `gamma``.group`

orbit-representatives of
the size `k` **maximal** complete subgraphs of `gamma`.

If `alls`=2 and `maxi`=`false`

, then `K` will be a set of `gamma``.group`

orbit-representatives of the size `k` complete subgraphs of `gamma`.
If `alls`=2 and `maxi`=`true`

then `K` will be a set of `gamma``.group`

orbit-representatives of the size `k` **maximal** complete subgraphs
of `gamma`. This option can be more costly than when `alls`=1.

The optional parameter `maxi` controls whether only maximal complete
subgraphs of size `k` are returned. The default is `false`

, which means
that non-maximal as well as maximal complete subgraphs of size `k` are
returned. If `maxi`=`true`

then only maximal complete subgraphs of size
`k` are returned. (Previous to version 4.1 of GRAPE, `maxi`=`true`

meant that it was assumed (but not checked) that all complete subgraphs
of size `k` were maximal.)

The optional boolean parameter `col` is used to determine whether or not
partial proper vertex-colouring is used to cut down the search tree. The
default is `true`

, which says to use this partial colouring. For backward
compatibility, `col` a rational number means the same as `col`=`true`

.

The optional parameter `wts` should be a list of vertex-weights; the list
should be of length `gamma``.order`

, with the `i`-th element being the
weight of vertex `i`. The weights must be all positive integers if `k`
is an integer, and all non-zero *d*-vectors of non-negative integers
if `k` is a *d*-vector. The default is that all weights are equal to 1.
(Recall that a complete subgraph of **size** `k` means a complete subgraph
whose vertex-weights sum to `k`.)

If `wts` is a list of integers, then this list must be `gamma``.group`

invariant, where the action permutes the list positions in the natural
way.

If `wts` is a list of *d*-vectors then we assume that `gamma``.group`

acts
on the set of all integer *d*-vectors by permuting vector positions, such
that, for all *v* in `[1..`

`gamma``.order]`

and all *g* in `gamma``.group`

,
we have *wts* [*v*^{g}] = *wts* [*v*]^{g} (where the first action is `OnPoints`

and for the second action, if *i*^{g}=*j* then (*wts* [*v*]^{g})[*j*]=*wts* [*v*][*i*]),
and that we also have *k* ^{g}=*k* . These assumptions are **not** checked
by the function, and the use of vector-weights is primarily for advanced
users of GRAPE.

An alternative name for this function is
`CliquesOfGivenSize`

indexCliquesOfGivenSize.

See also CompleteSubgraphs.

gap> gamma:=JohnsonGraph(6,2); rec( isGraph := true, order := 15, group := Group([ ( 1, 6,10,13,15, 5)( 2, 7,11,14, 4, 9)( 3, 8,12), ( 2, 6)( 3, 7)( 4, 8)( 5, 9) ]), schreierVector := [ -1, 2, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1 ], adjacencies := [ [ 2, 3, 4, 5, 6, 7, 8, 9 ] ], representatives := [ 1 ], names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 1, 6 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 2, 6 ], [ 3, 4 ], [ 3, 5 ], [ 3, 6 ], [ 4, 5 ], [ 4, 6 ], [ 5, 6 ] ], isSimple := true ) gap> CompleteSubgraphsOfGivenSize(gamma,4); [ [ 1, 2, 3, 4 ] ] gap> CompleteSubgraphsOfGivenSize(gamma,4,1,true); [ ] gap> CompleteSubgraphsOfGivenSize(gamma,5,2,true); [ [ 1, 2, 3, 4, 5 ] ] gap> delta:=NewGroupGraph(Group(()),gamma);; gap> CompleteSubgraphsOfGivenSize(delta,5,2,true); [ [ 1, 2, 3, 4, 5 ], [ 1, 6, 7, 8, 9 ], [ 2, 6, 10, 11, 12 ], [ 3, 7, 10, 13, 14 ], [ 4, 8, 11, 13, 15 ], [ 5, 9, 12, 14, 15 ] ] gap> CompleteSubgraphsOfGivenSize(delta,5,0); [ [ 1, 2, 3, 4, 5 ] ] gap> CompleteSubgraphsOfGivenSize(delta,5,1,false,true, > [1,2,3,4,5,6,7,8,7,6,5,4,3,2,1]); [ [ 1, 4 ], [ 2, 3 ], [ 3, 14 ], [ 4, 15 ], [ 5 ], [ 11 ], [ 12, 15 ], [ 13, 14 ] ]

`MaximumClique( `

` )`

This function returns a maximum clique of the graph `gamma`, which must
be simple. A **maximum clique** indexmaximum clique of `gamma` is a
set of pairwise adjacent vertices of `gamma` of the largest possible size.

An alternative name for this function is
`MaximumCompleteSubgraph`

indexMaximumCompleteSubgraph.

See also CompleteSubgraphsOfGivenSize.

gap> J:=JohnsonGraph(5,2); rec( adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ], group := Group([ (1,5,8,10,4) (2,6,9,3,7), (2,5)(3,6)(4,7) ]), isGraph := true, isSimple := true, names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], order := 10, representatives := [ 1 ], schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1 ] ) gap> MaximumClique(J); [ 1, 2, 3, 4 ]

`CliqueNumber( `

` )`

This function returns the clique number of the given graph `gamma`,
which must be simple. The **clique number** indexclique number of
`gamma` is the size of a largest clique in `gamma`, where a **clique**
is a set of pairwise adjacent vertices.

gap> CliqueNumber(JohnsonGraph(5,2)); 4 gap> CliqueNumber(JohnsonGraph(6,2)); 5 gap> CliqueNumber(JohnsonGraph(7,2)); 6

[Up] [Previous] [Next] [Index]

grape manual

June 2018