CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Structured families of graphs and digraphs: characterizations, algorithms and partition problems
Org: César Hernández-Cruz (CINVESTAV, Mexico)

Arboricity and feedbacks sets in cographs  [PDF]

Arboricity is a graph parameter akin to chromatic number, in that it seeks to partition the vertices into the smallest number of sparse subgraphs. Where for the chromatic number we are partitioning the vertices into independent sets, for the arboricity we want to partition the vertices into forests. Arboricity is NP-hard in general, so we study the problem in the case of cographs. We present results regarding arboricity at most two and partial results about the general case. We also analyse the problem of finding a $q$-colourable feedback set in cographs, generalizing the problem of the independent feedback set.

The evolution of the structure of ABC-minimal trees  [PDF]

The atom-bond connectivity (ABC) index is a degree-based molecular descriptor that found diverse chemical applications. Characterizing trees with minimum ABC-index is the main open problem in this area. In this paper, we describe the exact structure of ABC-minimal trees with sufficiently many vertices and we show how their structure evolves when the number of vertices grows. We show that their radius is at most $5$ and all but at most $O(1)$ vertices have degree 1, 2, 4, or 53. This is a joint work with MohammadBagher Ahmadi and Bojan Mohar.

JING HUANG, University of Victoria
Graph and digraph classes arising from list homomorphism problems  [PDF]

The dichotomy of list homomorphism problems for graphs is well-understood. In particular, we understand exactly the graphs for which list homomorphism problems are polynomial time solvable. These include several well-studied graph classes. However, the digraphs which define the dichotomy of list homomorphism problems for digraphs are not completely comprehended. We exhibit several classes of digraphs which share a common forbidden structure and for which the list homomorphism problems are polynomial time solvable. Surprisingly, the forbidden structure gives rise to beautiful bipartite analogue of the classical comparability graphs. This contains joint work with Hell, Feder, Lin, McConnell, and Rafiey.

MAHDIEH MALEKIAN, Simon Fraser University
The structure of graphs with no $H$-immersion  [PDF]

Arguably the most well known result regarding graph minors is the Kuratowski-Wagner Theorem, which characterizes planar graphs as those excluding $K_{3,3}$ and $K_5$ as minors. Further, precise structure of $H$-minor free graphs is known for some small graphs $H$, most famously when $H$ is one of $K_4$, $K_5$, $K_{3,3}$, $W_4$, $W_5$, Prism, or the Cube. In the setting of graph immersions, however, there was a lack of such precise characterizations prior to our work. In this talk, I will present results describing $H$-immersion free graphs, where $H$ is one of $K_4$, $W_4$, Prism, or $K_{3,3}$.

Joint work with Matt DeVos.