CanaDAM 2021
On-line, May 25 - 28, 2021

Structural Graph Theory

MICHAEL BARRUS, University of Rhode Island
Unigraphs and hereditary graph classes  [PDF]

A unigraph is a graph that is the unique realization of its degree sequence up to isomorphism. Most graphs are not unigraphs, but the class of unigraphs contains several remarkable families of graphs, such as the threshold graphs, the matroidal graphs, and the matrogenic graphs.

Though each of these subclasses is hereditary, the class of unigraphs itself is not hereditary, though it ``almost'' is. We characterize the largest hereditary subclass and the minimal hereditary superclass of the unigraphs. We will see that like the classes of threshold, matroidal, and matrogenic graphs, these larger hereditary classes have several alternate characterizations in terms of forbidden subgraphs, structural decompositions, and degree sequence conditions.

FERNANDO ESTEBAN CONTRERAS-MENDOZA, Universidad Nacional Autónoma de México
Forbidden subgraph characterization for $(\infty,k)$-polar cographs  [PDF]

A graph without induced paths of length four is called a cograph. An $(s,k)$-polar partition of a graph is a partition $(A, B)$ of its vertex set such that $A$ induces a complete multipartite graph with at most $s$ parts, and $B$ induces the disjoint union of at most $k$ complete graphs. A graph is said to be $(s,k)$-polar if it admits an $(s,k)$-polar partition; $(s,\infty)$- and $(\infty,k)$-polar graphs can be analogously defined.

In this talk, we will focus on the problem of characterizing the $(\infty,k)$-polar cographs (for a fixed $k$) by means of a finite family of forbidden subgraphs. We will show a partial recursive construction for such obstructions, and we will give complete lists of them for the cases $k=2$ and $k=3$.

TERRY MCKEE, Wright State University, Dayton Ohio
Graphs in which every cycle has a `major chord'  [PDF]

Define a graph to be majorly chordal if every cycle of length $k \ge 4$ has a major chord, meaning a $\lfloor \frac{k}{2}\rfloor$-chord of the $k$-cycle. Majorly chordal graphs are always chordal, but this newly-named graph class is incomparable with the long-studied class of strongly chordal graphs. In spite of that discord, I'll show a certain harmony between these two notions, along with a forbidden induced subgraph characterization of the majorly chordal graphs.

ELHAM ROSHANBIN, Alzahra University
Burning number of some families of graphs  [PDF]

Graph burning is a graph process that is defined on the vertex set of a simple finite graph $G$ (It in fact can be seen as a model for the spread of any sort of influence among the members of a social network that are now represented by the vertices of $G$). The burning number of $G$ is the minimum number of steps that is needed in a graph burning process for $G$, and is denoted by $b(G)$. In this talk, we consider the graph burning problem for caterpillars and the asymptotic value of the burning number for the caterpillars in a random space. We also consider the burning number of $n$-dimensional hypercubes and show that a conjecture on the burning number of $n$-cubes indeed had been proved many years ago in a paper by Noga Alon. This is joint work with Yong Gao and Pawel Pralat.

MILOŠ STOJAKOVIĆ, University of Novi Sad
Structural properties of bichromatic non-crossing matchings  [PDF]

Given a set of $n$ red and $n$ blue points in the plane, we are interested in matching red points with blue points by straight line segments so that the segments do not cross. We develop a range of tools for dealing with the non-crossing matchings of points in convex position. It turns out that the points naturally partition into groups that we refer to as orbits, with a number of properties that prove useful for studying and efficiently processing the non-crossing matchings.

Bottleneck matching is such a matching that minimizes the length of the longest segment. Illustrating the use of the developed tools, we show how to solve the problem of finding bottleneck matchings of points in convex position faster than before.

Joint work with Marko Savić.