Events Search and Views Navigation
October 2021
Atlantic Graph Theory Seminar: Anthony Bonato (Ryerson University)
In pursuit-evasion games, a set of pursuers attempts to locate, eliminate, or contain an evader in a network. The rules, specified from the outset, greatly determine the difficulty of the questions posed above. For example, the evader may be visible, but the pursuers may have limited movement speed, only moving to nearby vertices adjacent to them. Central to pursuit-evasion games is the idea of optimizing certain parameters, whether they are the search number, burning number, or localization number, for example.…
Find out more »Atlantic Graph Theory Seminar: Danny Dyer (Memorial University)
Title: The basics of the deduction game Abstract: The deduction game is a new variant of the classical chasers and runners game where the chasers are trying to catch an invisible runner quickly, but with no communication possible between chasers on different vertices. Instead, chasers may deduce where their fellow chasers *must* move, and make corresponding adjustments to their own movements. The goal is to use as few chasers as possible, and in some cases that number is quite high. We…
Find out more »Atlantic Graph Theory Seminar: Viresh Patel (University of Amsterdam)
Title: Path decompositions of random directed graphs In this talk we consider the problem of partitioning the edges of a digraph into as few paths as possible. The minimum number of paths needed in such an edge decomposition is called the path number of the digraph. The problem of determining the path number is generally NP-hard. However, there is a simple (easy to compute) lower bound for the path number of a digraph in terms of its degree sequence, and…
Find out more »Atlantic Graph Theory Seminar: Guss Regts (University of Amsterdam)
Improved bounds for zeros of the chromatic polynomial on bounded degree graphs About 20 years ago Sokal proved that there exists a constant C so that for any graph G, all of the complex zeros of its chromatic polynomial are contained in the disk of radius C Delta(G) centered at 0. (Here Delta(G) denotes the maximum degree of G.) He showed that C could be taken slightly smaller than 8. This was improved to 6.91 by Fernández and Procacci. In this…
Find out more »November 2021
Atlantic Graph Theory Seminar: Jo Ellis-Monaghan (University of Amsterdam)
2017 saw the centennial of William Tutte, one of the greatest mathematicians of modern times. One of the testimonies to Tutte’s genius is that nearly everything he did proved to be a catalyst, triggering an explosion of further investigations and opening whole new vistas of mathematics. The Tutte polynomial is one of many such examples in his legacy. Here we will explore some of its salient properties and some of the many directions that propagated outward from the original Tutte…
Find out more »Atlantic Graph Theory Seminar: Pavol Hell (SFU)
I will discuss a few examples where considering loops leads to interesting insights, often allowing unifying existing results. These examples will include cops and robbers games, graph homomorphisms, variants of interval and chordal graphs, and versions of domination. Join Zoom Meeting: link
Find out more »December 2021
Atlantic Graph Theory Seminar: James Preen (Cape Breton University)
There are many results about triangles in graphs, but the property that every edge in a graph is in at least one triangle seems not to have been studied before. The 4-regular case was quickly solved collaboratively following an internet posting and then written about by one author in their blog, before being published in the Journal of Graph Theory in 2013. However, the result that was originally wanted was a characterisation for 5-regular graphs, and that did not emerge…
Find out more »