Graph Polynomials  Part I
Org:
Iain Beaton (Dalhousie University) et
Ben Cameron (University of Guelph)
[
PDF]
 IAIN BEATON, Dalhousie University
On the Unimodality of Domination Polynomials [PDF]

A polynomial is said to be unimodal if its coefficients are nondecreasing and then nonincreasing. 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 2EdgeColoured Graphs [PDF]

In this talk we extend the definition of chromatic polynomial to 2edgecoloured 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 nonnegative 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 ClawContractibleFree 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 wellbehaved — 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 clawfree graphs the coefficient sequence is logconcave.
Open since 1987 is the question (due to Alavi et al.) of whether trees and forests have independence polynomials with logconcave 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. https://arxiv.org/pdf/2102.00268.pdf