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

In honour of Pavol Hell - Part I
Org: Gary MacGillivray (University of Victoria)

KATHIE CAMERON, Wilfred Laurier University
A Parity Theorem About Trees with Specified Degrees  [PDF]

Thomassen and I proved that the number of cycles containing a specified edge and all the odd-degree vertices is odd if and only if graph G is eulerian. Where all vertices have even degree this is Toida's Theorem and where all vertices have odd degree it is Thomason's generalization of Smith's Theorem. Berman extended Thomason’s Theorem to trees, proving that if T is a spanning tree of G where all degrees in G-E(T) are even, there is an even number of spanning trees with the same degree as T at each vertex. I give a common generalization of these results.

SHENWEI HUANG, Nankai University
k-critical graphs in P5-free graphs  [PDF]

A graph $G$ is $k$-vertex-critical if $G$ has chromatic number $k$ but every proper induced subgraph of $G$ has chromatic number less than $k$. We will talk about the finiteness of $k$-vertex-critical graphs in subclasses of $P_5$-free graphs. Our main result is a complete classification of the finiteness of $k$-vertex-critical graphs in the class of $(P_5,H)$-free graphs for all graphs $H$ on 4 vertices. To obtain the complete dichotomy, we prove the finiteness for four new graphs $H$ using various techniques -- such as Ramsey-type arguments and the dual of Dilworth's Theorem -- that may be of independent interest.

JAROSLAV NEŠETŘIL, Charles University
In praise of homomorphisms  [PDF]

Related to a recent survey with P. Hell (Comp. Sci. Review 2021) we highlight some aspects of development of this exciting area of mathematics and theoretical computer science.

ARASH RAFIEY, Indiana State University
2-SAT and Transitivity Clauses  [PDF]

We show that every instance of 3-SAT is polynomial-time equivalent to an instance of 2-SAT together with transitivity clauses, 2-SAT-Trans. More precisely, every 3-SAT instance is polynomially equivalent to an instance with variables $X_{i,j}, i \ne j \in [1,n] \ \ ( X_{i,j} \equiv \lnot X_{j,i}$) and all the clauses of form $(X_{i,j} \lor X_{j,k} \lor X_{k,i}) \land (X_{j,i} \lor X_{k,j} \lor X_{i,k})$ together with some two variables clauses. We show several graph vertex ordering problems are instances of 2-SAT-Trans. Our goal is to specify the 2-SAT-Trans instances that are polynomial.

Based on joint works with Pavol Hell and co-authors.

XUDING ZHU, Zhejiang Normal University
On Hedetniemi's Conjecture  [PDF]

Hedetniemi conjectured that if none of $G$ and $H$ is $c$-colourable, then $G \times H$ is not $c$-colourable. This conjecture remained open for more than half century, until Shitov proved in 2019 that it fails for huge $c$. Shortly after, this author found smaller counterexamples, showed that Hedetniemi's conjecture fails for $c\ge 125$, and then by Tardif to $c \ge 13$, and then by Wrochna to $c \ge 5$. In the other direction, El-Zahar and Sauer showed that Hedetniemi's conjecture holds for $c \le 3$. I shall sketch ideas, explain the similarities and differences in these proofs.