- This event has passed.
Atlantic Graph Theory Seminar
January 31, 2024 @ 3:30 pm - 4:30 pm
Speaker: Thiago de Holleben, Dalhousie University
Title: Homological invariants of graphs with no induced cycles of length divisible by 3
Abstract: If G is a graph with large chromatic number, what can we say about its induced subgraphs? In 2014, Bonamy et al. showed that if a graph has no induced cycles of length divisible by three, then its chromatic number is bounded. Such graphs are called ternary.
In an attempt to better understand the structure of the induced subgraphs of a graph with bounded chromatic number, Kalai and Meshulam posed questions relating topological invariants of the independence complex, and the chromatic number of a graph. Since then, there have been several results bounding chromatic numbers of graphs using topology. In 2022, Jinha Kim showed a conjecture of Engström stating the exact topological structure of the independence complex of a ternary graph. In this talk, we describe a graph theoretic way of computing this structure. As an application, we show that -1 is a root of the independence polynomial of a forest F if and only if the induced matching number of F is not equal to the domination number of F.
Join Zoom Meeting
Meeting ID: 864 1523 0827
Passcode: 835547