Graph Fall-Colouring: Some New Perspectives

Graph Fall-Colouring is the problem of partitioning a graph into independent dominating sets. Unlike typical graph-theoretic problems, this partition may not always exist. In this talk, we will review some constructions of fall-colourable graphs with many different fall-colourings. We will also look at some new constructions of graphs with distinct fall-colourings and non-fall-colourings. Additionally, we will revisit some results for graph families which can be shown to be fall-colourable.

Finally, we will talk about the related topic of fall-near-colouring, which relaxes the independence requirement. Here, the vertices of a graph are partitioned into dominating sets, and the attempt is to bound the maximum degree induced by each such set.

Event Topic

Discrete Applied Math Seminar