Skip to main content
To KTH's start page To KTH's start page

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

Time: Wed 2023-06-14 09.30 - 10.00

Location: 3418, Lindstedsvägen 25 and Zoom

Video link:

Respondent: Santiago Díaz de Argandoña Muñoz

Export to calendar


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.