CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Graph Structure and Algorithms
Org: Kathie Cameron (Wilfrid Laurer University) et Shenwei Huang (Nankai University)

KATHIE CAMERON, Wilfrid Laurer University
Hadwiger's Conjecture for (Cap, Even Hole)-Free Graphs  [PDF]

A minor of a graph $G$ is obtained from a subgraph of $G$ by contracting edges. In 1943, Hadwiger made his famous conjecture (HC): For every integer $t \ge 0$, every graph with no $K_{t+1}$ minor is $t$-colourable. Hadwiger proved the conjecture for $t=3$. For $t=4$, it is equivalent to the Four Colour Theorem. Robertson, Seymour and Thomas proved it for t=5. For $t \ge 6$, it remains open. Chudnovsky and Fradkin proved HC for quasi-line graphs. We prove HC for (cap, even hole)-free graphs, and for some related classes of graphs. This is joint work with Kristina Vu\v{s}kovi\'c.

On the Pancyclicity of $k$-quasi-transitive Digraphs ofLlarge Diameter  [PDF]

A digraph is $k$-quasi-transitive if for every $uv$-directed path of length $k$ in $D$, the vertices $u$ and $v$ are adjacent. Wang and Zhang proved that, for even $k$, every $k$-quasi-transitive digraph of diameter at least $k+2$ has a Hamiltonian path, and asked whether it is possible to prove the existence of a Hamiltonian cycle under the same assumptions. In this talk we answer this question in the positive, and additionally prove that a digraph with these characteristics is indeed pancyclic.

This is joint work with Manuel Alejandro Ju\'arez-Camacho.

PAVOL HELL, Simon Fraser University
Bipartite Analogues of Comparability and Co-comparability Graphs  [PDF]

I will discuss bigraph analogues of these graph classes. Surprisingly, in the context of bipartite graphs, they turn out to define the same class. I will mention characterizations in terms of orderings, orientations, and forbidden substructures. These definitions, together with some concepts introduced earlier, create a bipartite world in which one can find analogues of traditional results about graph classes. For instance, we find a bipartite analogue of the fact that the class of interval graphs is the intersection of the classes of cocomparability graphs and chordal graphs.

This is joint work with Jing Huang, Jephian Lin, and Ross McConnell.

OWEN MERKEL, University of Waterloo
An optimal $\chi$-Bound for ($P_6$, diamond)-free graphs  [PDF]

Given two graphs $H_1$ and $H_2$, a graph is $(H_1,H_2)$-free if it contains no induced subgraph isomorphic to $H_1$ or $H_2$. Let $P_t$ be the path on $t$ vertices and $K_t$ be the complete graph on $t$ vertices. The diamond is the graph obtained from $K_4$ by removing an edge. We show that every ($P_6$, diamond)-free graph $G$ satisfies $\chi(G)\le \omega(G)+3$, where $\chi(G)$ and $\omega(G)$ are the chromatic number and clique number of $G$, respectively. This bound is tight and is attained by the complement of the 27-vertex Schläfli graph. This is joint work with Kathie Cameron and Shenwei Huang.

JURAJ STACHO, Google Zurich
3-colorable Subclasses of $P_8$-free Graphs  [PDF]

We study 3-colorable graphs having no induced 8-vertex path $P_8$ and no induced cycles $C_k$ of two specific small lengths $k$. We characterize three such cases. Namely, we show that if no $C_3$ and no $C_4$ are allowed, then by way of structural decomposition, all such graphs are 3-colorable. Same holds for the case where no $C_3$ and no $C_5$ are allowed. For the case with no $C_4$ and no $C_5$, we find all critical graphs.

Joint work with Maria Chudnovsky.