CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017

Graph Polynomials
Org: Jason Brown (Dalhousie University)

JASON BROWN, Dalhousie University
Recent Results on Chromatic Polynomials  [PDF]

The chromatic polynomial of a finite graph $G$ counts the number of ways the vertices of a graph can be colored with x colours so that adjacent vertices receive different colors. Chromatic polynomials were initially introduced while working on the Four Color Conjecture, and have been studied not only for what they can say about chromatic theory but also as analytic and algebraic objects of interest in their own right. In this talk I will present recent work on new bounds for chromatic polynomials as well as results on the real part, imaginary part and moduli of their roots.

BEN CAMERON, Dalhousie University
On the Unimodality of Independence Polynomials of Very Well-Covered Graphs  [PDF]

The independence polynomial of a graph is the generating function of the numbers of independent sets of each size. A graph of order $n$ is very well-covered if every maximal independent set has size $\frac{n}{2}$. Levit and Mandrescu conjectured that the independence polynomial of every very well-covered graph is unimodal. In this talk we will show that every graph is embeddable as an induced subgraph of a very well-covered graph whose independence polynomial is unimodal, by considering the location of the roots of such polynomials. This is a joint work with Jason Brown of Dalhousie University.

DANIELLE COX, Mount Saint Vincent University
Optimality Results for Graph Polynomials  [PDF]

One of the many topics one can investigate regarding graph polynomials is the existence of optimal polynomials on a domain, $D$. In this talk we will discuss some known optimality results as well as some new ones for a variety of graph polynomials, such as the independence polynomial, chromatic polynomial and reliability polynomials.

LUCAS MOL, University of Winnipeg
Roots of all-terminal reliability and node reliability polynomials  [PDF]

Given a graph $G$ in which nodes are perfectly reliable but each edge fails independently with probability $q\in[0,1],$ the all-terminal reliability of $G$ is the probability that all nodes can communicate with one another. If instead the edges are perfectly reliable but each node fails independently with probability $q$, then the node reliability of $G$ is the probability that the operational nodes can all communicate with one another in the graph that they induce. In this talk, we present some new results on the roots of each of these polynomials which indicate major differences between these models of reliability.

DAVID WAGNER, University of Waterloo
The algebra of flows in graphs  [PDF]

We give a simple and more explicit description of a graded algebra defined in terms of a graph $G$ nearly $20$ years ago. If $G$ has $n$ vertices and $c$ components, then the Poincar\'e polynomial of this algebra is the specialization $t^{n-c}T(G;t^{-1},1+t)$ of its Tutte polynomial. Recent calculations by Ghislain McKay show that for all simple graphs with up to nine vertices, the sequence of coefficients of this polynomial is logarithmically concave. I will discuss one current approach towards the conjecture that this holds for all graphs.


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