Santiago Díaz de Argandoña Muñoz: Counting k-strict graph colourings

Abstract.

Given a finite graph and a positive integer k, we consider vertex colourings with integer colors between 1 and t such that the difference of the colors of two adjacent vertices is at least k. Using polyhedral-geometric methods, we show that the function that counts such colourings eventually agrees with a polynomial. Furthermore, we also consider the question when the difference is calculated in modular arithmetic. The function that counts these colourings is also eventually a polynomial. We will show some properties of this polynomial by making a connection to hyperplane arrangements.