CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017

Colourings, Homomorphisms and Forbidden Structures

JAN FONIOK, Manchester Metropolitan University
Pultr functors and chromatic numbers  [PDF]

It has long been known that the chromatic number of the $n$-th \emph{shift graph} is logarithmic in $n$; more generally, the chromatic number of the \emph{arc graph} of a digraph $G$ is logarithmic in the chromatic number of $G$. Recently, Avart, Kay, Łuczak, Reiher and Rödl have determined the chromatic numbers of ‘generalised shift graph’.

These generalised shift graphs can be viewed as the result of an application of a Pultr functor to the transitive tournaments, in the same way as shift graphs are the result of an application of the arc-graph functor to transitive tournaments. What are the chromatic numbers of graphs obtained by applying these functors to other digraphs? How about other Pultr functors, not covered by the above results? In my talk I will discuss these results and questions, as well as present some open problems.

ISLEM GHAFFOR, University of Science and Technology of Oran
Counting Twin Primes  [PDF]

In this talk we give two new formulae which count exactly the quantity of twin primes not greater than a certain given value $36n^2+60n+21$ and $p_n^2-3$. We use in these formulae the arithmetic progressions and the cardinality. In the first formula, we do not need to make any "primality" test and in the second formula we use the n-th prime number and we show the relation between counting primes and twin primes. We would also say that we have produced new algorithms to make such count.

MARTINA MOCKOVCIAKOVA, University of West Bohemia, Pilsen, Czech Republic
Star edge-coloring of subcubic graphs  [PDF]

A star edge-coloring of a graph is a proper edge-coloring without bichromatic paths and cycles of length four. In 2013 Dvo\v{r}\'{a}k, Mohar, and \v{S}\'{a}mal showed that 7 colors are enough for a star edge-coloring of subcubic graphs. They suggested to study a list version of this problem and asked whether 7 colors are enough also for list star edge-coloring of subcubic graphs.

In this talk, we discuss results regarding subcubic graphs and prove that the list star chromatic index of such graphs is at most 7, answering the question above.

ALI PAZOKI, Simon Fraser University
Irreflexive oriented trees with a min ordering  [PDF]

Min ordering of a digraph $H$ plays an important role in deciding the existence of a list homomorphism to $H$. For reflexive oriented trees $H$, Feder, Hell, Huang and Rafiey gave a concrete forbidden induced subgraph condition to have a min ordering. For irreflexive oriented trees $H$, the existence of a min-ordering turned out to be somewhat harder, as there are many types of obstructions. In this presentation, we will give a simple structural characterization of irreflexive oriented trees with a min ordering. This is joint work with Pavol Hell and Arash Rafiey.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Ryerson Office of Naval Research Science and Technology