Structured families of graphs and digraphs: characterizations, algorithms and partition problems Org: César Hernández-Cruz (CINVESTAV, Mexico)
[PDF]
SEBASTIÁN GONZÁLEZ HERMOSILLO DE LA MAZA, Simon Fraser University 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.
SEYYED ALIASGHAR HOSSEINI, Simon Fraser University 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}$.