Graph Structure and Algorithms
Org:
Kathie Cameron (Wilfrid Laurer University) and
Shenwei Huang (Nankai University)
[
PDF]
 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 quasiline 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.
 CÉSAR HERNÁNDEZ CRUZ, CINVESTAV Mexico
On the Pancyclicity of $k$quasitransitive Digraphs ofLlarge Diameter [PDF]

A digraph is $k$quasitransitive 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$quasitransitive 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\'arezCamacho.
 PAVOL HELL, Simon Fraser University
Bipartite Analogues of Comparability and Cocomparability 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 27vertex Schläfli graph. This is joint work with Kathie Cameron and Shenwei Huang.
 JURAJ STACHO, Google Zurich
3colorable Subclasses of $P_8$free Graphs [PDF]

We study 3colorable graphs having no induced 8vertex 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 3colorable. 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.