Department of
Applied
Mathematics

Interlacing adjoints of tournaments

Claude Tardif

Royal Military College of Canada

Abstract

The k-th interlacing adjoint of the transitive tournament Tn (n > 2k) Is the digraph i(k,Tn) defined as follows: Its vertices are the sequences (a1, ..., ak) such that 1 <= a1 < a2 < ... < ak <= n, and there is an arc from (a1, ..., ak) to (b1, ..., bk) if a1 < b1 < a2 < b2 < ... < ak < bk.

We will discuss chromatic numbers of interlacing adjoints of transitive tournaments, and relations to adjoint functors, finite duality, graph colouring heuristics and chromatic numbers of products of graphs.

This is joint work with Jan Foniok and Jaroslav Nesetril.