CanaDAM 2021
En ligne, 25 - 28 mai 2021

Graph Polynomials - Part I
Org: Iain Beaton (Dalhousie University) et Ben Cameron (University of Guelph)

IAIN BEATON, Dalhousie University
On the Unimodality of Domination Polynomials  [PDF]

A polynomial is said to be unimodal if its coefficients are non-decreasing and then non-increasing. The domination polynomial of a graph $G$ is the generating function of the number of domination sets of each cardinality in $G$, and its coefficients have been conjectured to be unimodal. In talk paper we will show the domination polynomial of paths and cycles are unimodal, and that the domination polynomial of almost every graph is unimodal with mode $\lceil \frac{n}{2}\rceil $. This joint work with Jason Brown.

DANIELLE COX, Mount Saint Vincent University
Chromatic Polynomials of 2-Edge-Coloured Graphs  [PDF]

In this talk we extend the definition of chromatic polynomial to 2-edge-coloured graphs. We will provide results regarding the computation of the polynomial as well as discuss the location of roots. This is joint work with Chris Duffy (University of Saskatchewan) and Iain Beaton (Dalhousie University).

SAMANTHA DAHLBERG, Arizona State University
Chromatic symmetric functions and $e$-positivity  [PDF]

Richard Stanley introduced the chromatic symmetric function $X_G$ of a simple graph $G$, an algebraic encoding of all possible proper colorings with colors $\{1,2,3,\dots \}$. These formal power series are symmetric functions that generalize the chromatic polynomial. In this talk we discuss the algebraic property of $e$-positivity, when $X_G$ can be written as a non-negative sum of elementary symmetric functions. We will also discuss what is known about $e$-positivity, and additionally we will resolve Stanley's $e$-Positivity of Claw-Contractible-Free Graphs. This is joint work with Angele Foley and Stephanie van Willigenburg.

DAVID GALVIN, University of Notre Dame
The independence polynomial of the random tree  [PDF]

The independence polynomial of a graph is not in general well-behaved — Alavi et al. showed, for example, that its coefficient sequence can exhibit arbitrary patterns of rises and falls. For some restricted families, things are much nicer — Hamidoune, for example, showed that for claw-free graphs the coefficient sequence is log-concave.

Open since 1987 is the question (due to Alavi et al.) of whether trees and forests have independence polynomials with log-concave coefficient sequences. I’ll report on some recent work around this problem, joint with Abdul Basit, where we focus on the independence polynomial of the random tree.

JÁNOS MAKOWSKY, Technion - Israel Institute of Technology
Graph polynomials unimodular for almost all graphs.  [PDF]

Inspired by a recent result of I. Beaton and J. Brown (2020), which states that for almost all graphs the domination polynomial $D(G;x)$ has a unimodal sequence of coefficients, we study the same unimodality result for graph polynomials which are generating functions of a graph property $\mathcal{C}$ or a property of graphs with an additional relation $\mathcal{P}$.

THEOREM: Let $\mathcal{C}$ be the complement of a hereditary graph property, and let $ P_{\mathcal{C}}(G;X) = \sum_{A \subseteq V(G): G[A] \in \mathcal{C}} X^{|A|}. $ Then the coefficients of $P_{\mathcal{C}}(G;X)$ are unimodal for almost all graphs $G$.

Joint work with Vsevolod Rakita.