Matricial Construction of \(k – colourings\) on Square Lattice

J.M. Marin1, A. Marquez 1, M.P. Revuelta1
1Departamento de Matematica Aplicada I. Universidad de Sevilla (Spain).

Abstract

The paper contains two main results. First, we obtain the chromatic polynomial on the \(n \times m\) section of the square lattice, solving a problem proposed by Read and Tutte \([5]\), the chromatic polynomial of the bracelet square lattice, and we find a recurrent-constructive process for the matrices of the \(k\)-colourings. The key concept for obtaining the inductive method is the compatible matrix.

Our second main result deals with the compatible matrix as the adjacency matrix of a graph. This represents a family of graphs, which is described.