Avoiding uniform arrays and related problems of list-coloring edges

Graphs, Hypergraphs, and Computing

13 May 14:00 - 15:00

Lina Andrén - Umeå University

A Latin square of order n is an arrangement of the numbers 1,...,n in an n x n grid such that all the numbers appear exactly once in each row and each column. In this seminar I will present a technique for finding Latin squares subject to certain kinds of restrictions, i. e. some numbers may be forbidden in every cell. The problem translates to a list-coloring problem for the edges of a complete bipartite graph. We used this technique to show that as long as the restrictions are such that no number is forbidden to many times in any row or column, there is a constant a<1 such that only a*n of the numbers need to be allowed in each cell. (In the light of the result of Galvin (1995) saying that the list-chromatic index of a bipartite graph is equal to its chromatic index, which implies that without any conditions on which numbers are forbidden and where, it is impossible to forbid even one number in each cell, it is clear that the conditions we apply on the restrictions are crucial.) I will also discuss some implications of such results for list-coloring the edges of certain graphs.

Joint work with Carl Johan Casselgren and Lars-Daniel Öhman.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to