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

# 7 Vertex-Colouring and Complete Subgraphs

### Sections

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, where the weights can be positive integers or non-zero vectors of non-negative integers.

## 7.1 VertexColouring

• `VertexColouring( `gamma` )`
• `VertexColouring( `gamma`, `k` )`
• `VertexColouring( `gamma`, `k`, `m` )`

This function returns a proper vertex-colouring C for the graph gamma, which must be simple. A proper 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]not=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
```

## 7.2 MinimumVertexColouring

• `MinimumVertexColouring( `gamma` )`

This function returns a minimum vertex-colouring C for the graph gamma, which must be simple. A minimum 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]not=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.

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

## 7.3 ChromaticNumber

• `ChromaticNumber( `gamma` )`

This function returns the chromatic number of the given graph gamma, which must be simple. The chromatic 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.

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

## 7.4 CompleteSubgraphs

• `CompleteSubgraphs( `gamma` )`
• `CompleteSubgraphs( `gamma`, `k` )`
• `CompleteSubgraphs( `gamma`, `k`, `alls` )`

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

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

## 7.5 CompleteSubgraphsOfGivenSize

• `CompleteSubgraphsOfGivenSize( `gamma`, `k` )`
• `CompleteSubgraphsOfGivenSize( `gamma`, `k`, `alls` )`
• `CompleteSubgraphsOfGivenSize( `gamma`, `k`, `alls`, `maxi` )`
• `CompleteSubgraphsOfGivenSize( `gamma`, `k`, `alls`, `maxi`, `col` )`
• `CompleteSubgraphsOfGivenSize( `gamma`, `k`, `alls`, `maxi`, `col`, `wts` )`

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 (positive) integers, then it is required that for all g in gamma`.group` and all v in `Vertices(`gamma`)`, we have wts[vg]=wts[v].

If wts is a list of d-vectors then we assume that there is some group G and epimorphism theta from G to gamma`.group`, such that there is an action mu of G on `[1..`d`]`, giving an action of G on the set of integer d-vectors, where if w is an integer d-vector and g in G then wg is defined by wg[mu(i,g)]=w[i] for all i in `[1..`d`]`. It is then required that for all g in G, we have kg=k and for all v in `Vertices(`gamma`)`, wts[vgtheta] = wts[v]g. These requirements are not checked by the function, and the use of vector-weights is primarily for the DESIGN package and advanced users of GRAPE.

An alternative name for this function is `CliquesOfGivenSize`.

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

## 7.6 MaximumClique

• `MaximumClique( `gamma` )`

This function returns a maximum clique of the graph gamma, which must be simple. A maximum 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`.

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

## 7.7 CliqueNumber

• `CliqueNumber( `gamma` )`

This function returns the clique number of the given graph gamma, which must be simple. The clique 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
March 2021