# Discrete Math Seminars

Most Fridays in K9509 - 11:30am to 12:30pm

Please join us for this weekly seminar on a wide variety of topics under the umbrella of discrete mathematics. We gratefully acknowledge the Pacific Institute of Mathematical Sciences for their generous funding since 2010.

Watch for upcoming Seminars listed below, offered in SCK 9509 and/or on Zoom. We welcome remote participation from groups at other universities.

All talks will be announced on this page, on the department calendar (found at the bottom of the Math homepage), and on the DM Seminar mailing list. If you have an SFU email address, you can subscribe or unsubscribe to the mailing list by logging in to maillist.sfu.ca and searching for the math-dmsem list. Otherwise, you can ask any discrete math faculty member to manually add you to the list. With the permission of the speaker, we will record the talk video and upload it to the SFU Discrete Math Seminar Youtube Channel

Current organizer: Bojan Mohar (mohar@sfu.ca) & Jesse Campion Loth

## 2023 Talks

### Spring 2023

 11 Jan Jesse Campion Loth, SFU Permutations, probability and graph embeddings Products of permutations are used to model problems in fields ranging from representation theory and algebraic geometry to topological graph theory.  I will show how probability can be used to study such problems.  I will start with some algebraic results on products of symmetric group conjugacy classes.  I will then show how these results can be used to solve natural topological problems.  The main focus of the talk will then be using these random techniques to study how graphs may be embedded on different surfaces. 18 Jan Shuxing Li, SFU Packings of Partial Difference Sets As the underlying configuration behind many elegant finite structures, partial difference sets have been intensively studied in design theory, finite geometry, coding theory, and graph theory. In the first part of this talk, I will showcase that partial difference sets are indeed the fundamental structures explaining a series of “two-valued phenomena” in various mathematical branches. The second part concerns the construction of partial difference sets. Over the past three decades, there have been numerous constructions using very dif- ferent and delicate approaches. Surprisingly, we discovered a common frame- work unifying and extending many previous constructions. This is joint work with Jonathan Jedwab. 2 Feb Prof. Dimitri Leemans, Université Libre de Bruxelles The number of string C-groups of high rank (Joint with Operations Research seminar) Abstract polytopes are a combinatorial generalisation of  classical objects that were already studied by the greeks. They consist  in posets satisfying some extra axioms. Their rank is roughly speaking  the number of layers the poset has. When they have the highest level of symmetry (namely the automorphism group has  one orbit on the set of maximal chains), they are called regular. One  can then use string C-groups to study them. Indeed, string C-groups are in one-to-one correspondence with  abstract regular polytopes. They are also smooth quotients of Coxeter  groups. They consist in a pair $(G,S)$ where $G$ is a group and $S$ is a  set of generating involutions satisfying a string property and an  intersection property. The cardinality of the set $S$ is the rank of the  string C-group. It corresponds to the rank of the associated polytope. In this talk, we will give the latest developments on the study of  string C-groups of high rank. In particular, if $G$ is a transitive  group of degree $n$ having a string C-group of rank $rgeq (n+3)/2$, work  over the last twelve years permitted us to show that $G$ is necessarily the symmetric group $S_n$. We have just proven in the last months that if $n$ is large enough,  up to isomorphism and duality, the number of string C-groups of rank  $r$ for $S_n$ (with $rgeq (n+3)/2$) is the same as the number of string  C-groups of rank $r+1$ for $S_{n+1}$. This result and the tools used in its proof, in particular the rank  and degree extension, imply that if one knows the string C-groups of  rank $(n+3)/2$ for $S_n$ with $n$ odd, one can construct from them all  string C-groups of rank $(n+3)/2+k$ for $S_{n+k}$ for any positive integer $k$. The classification of the string C-groups of rank $rgeq (n+3)/2$  for $S_n$ is thus reduced to classifying string C-groups of rank $r$ for  $S_{2r-3}$. A consequence of this result is the complete classification of all  string C-groups of $S_n$ with rank $n-kappa$ for $kappain{1,ldots,6}$,   when $ngeq 2kappa+3$, which extends previous known results. The number of string C-groups of rank $n-kappa$, with $ngeq 2kappa +3$, of this classification gives the following sequence of integers  indexed by $kappa$ and starting at $kappa = 1$. $$Sigma{kappa}=(1,1,7,9,35,48).$$ This sequence of integers is new according to the On-Line Encyclopedia of Integer Sequences. Joint work with Peter J. Cameron (University of St Andrews) and Maria Elisa Fernandes (University of Aveiro) 8 Feb Curtis Bright, University of Windsor SAT Solvers, Isomorph-free Generation, and the Quest for the Minimum Kochen–Specker System I will describe a new approach for exhaustively generating combinatorial objects by combining a satisfiability (SAT) solver with an isomorph-free exhaustive generation method such as orderly generation. The SAT solver is able to limit the search to objects that satisfy given criteria, while the isomorph-free generation method ensures that the objects are generated up to isomorphism. The combined search procedure performs orders-of-magnitude faster than a pure SAT or pure computer algebraic approach, as the SAT solver tailors the search to the object in question while the isomorph-free generation avoids duplication of work when the search space is highly symmetrical. As a motivating example, I will discuss how this approach can be applied to search for Kochen-Specker (KS) systems, an important combinatorial object arising in quantum physics.  For example, a KS system is at the heart of the "KS Theorem" which intuitively states that a quantum observation cannot be understood as revealing a pre-existing value, and the "Free Will Theorem" which intuitively states that if humans have free will then so must quantum particles. Since 1990, the smallest known KS system in three dimensions has contained 31 vectors and much effort has been expended trying to find a KS system of smaller size.  An exhaustive computer search in 2016 was able to disprove the existence of a KS system of 21 or fewer vectors. Our SAT and orderly generation approach is over 25,000 times faster than the previously used approach and has also ruled out the existence of a KS system with 22 vectors. This work is joint with Zhengyu Li and Vijay Ganesh (University of Waterloo). 15 Feb Stephen Kobourov, University of Arizona Contact Representation of Planar Graphs in 2D and 3D In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. We show how to use Schnyder realizers and canonical orders for planar graphs to obtain different types of contact representations. Specifically, we describe an algorithm that constructs proportional contact representation for arbitrary planar graphs using 10-sided rectilinear polygons. We also describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity, as 8-sided polygons are sometimes necessary. In 3D vertices are represented by polytopes and edges by contacts between the corresponding polytopes contacts. We show that planar 3-trees have contact representations with cubes and proportional contact representations with boxes. 8 Mar Harmony Zhan, SFU On trees with extremal second largest eigenvalues We will characterize members that maximize/minimize the second largest adjacency eigenvalue in certain families of trees. Joint work with H. Kumar, B. Mohar and S. Pragada. 15 Mar Zhilin Ge, SFU Hamiltonicity of Covering Graphs of Trees We consider covering graphs obtained by lifting trees as voltage graphs over cyclic groups. We generalize a tool of Hell, Nishiyama, and Stacho, known as the billiard strategy, for constructing Hamiltonian cycles in the covering graphs of paths. The presentation will show that our extended tool can be used to provide new sufficient conditions for the Hamiltonicity of covering graphs of trees that are similar to those of Batagelj and Pisanski and of Hell, Nishiyama, and Stacho. Next, we focus specifically on covering graphs obtained from trees lifted as voltage graphs over cyclic groups Zp of large prime order p. The presentation will show that for a given reflexive tree T with random nonzero voltage labels from Zp on its edges, the corresponding lift is almost surely Hamiltonian for a large enough prime-ordered cyclic group Zp. Finally, we show that if a reflexive tree T is lifted over a group Zp of a large prime order, then for any assignment of nonzero elements of Zp to the edges of T, the corresponding cover of T has a large circumference.

## 2022 Talks

### Fall 2022

 07 Oct Special Time: 11am Bojan Mohar. Simon Fraser University Beyond the Four-Color Theorem The speaker will discuss the Four-Color Theorem and some of the outstanding problems left open after the proof. 14 Oct Peter Bradshaw, Simon Fraser University A small step forward in bipartite list coloring The choosability of a graph G is the minimum value k such that G has a proper list coloring whenever each vertex of G has a list of k colors. Molloy showed that if G is a triangle-free graph of maximum degree d, then the choosability of G is at most (1 + o(1)) d / log d and that this bound is tight within a factor of roughly 2. It is widely believed that this upper bound can be greatly improved in the special case that G is bipartite, and Alon and Krivelevich conjectured an upper bound of O(log d) in this case. However, little progress has been made toward solving this conjecture, and it is currently unknown whether the optimal upper bound for bipartite graphs is different from the optimal upper bound for triangle-free graphs. In this talk, we will use a modification of a coupon-collector argument from Alon, Cambie, and Kang to show that every bipartite graph of maximum degree d has choosability at most 0.797 d / log d. Our result provides strong evidence that the list-coloring problem is fundamentally easier in bipartite graphs than in triangle-free graphs and hence takes an important step toward solving the conjecture of Alon and Krivelevich. (The content of this talk is part of ongoing work with Bojan Mohar and Ladislav Stacho.) 21 Oct Harmony Zhan, Simon Fraser University An introduction to discrete quantum walks A discrete quantum walk is determined by a unitary matrix representation of a graph. In this talk, I will give an overview of different quantum walks, and show how the spectral information of the unitary matrix representation links properties of the walks to properties of the graphs. Part of this talk will be based on the book, Discrete Quantum Walks on Graphs and Digraphs, by Chris Godsil and me. 28 Oct Zhouningxin Wang Circular flows in mono-directed Eulerian signed graphs In this talk, we consider analogs of Jaeger's circular flow  conjecture and its dual Jaeger-Zhang conjecture in signed graphs. We  will first give the notions of circular coloring and circular flow in  signed graphs, and then show that every (6k-2)-edge-connected Eulerian signed graph admits a circular 4k/(2k-1)-flow and that every  signed bipartite planar graph of negative-girth at least 6k-2 admits a  circular 4k/(2k-1)-coloring (equivalently, admits a homomorphism to a  negative cycle of length 2k). We also provide some recent results about circular flow indices of signed graphs with  high edge-connectivities.  This is based on joint work with Jiaao Li, Reza Naserasr, and Xuding Zhu. 4 Nov Dong Ye, Middle Tennessee State University Nowhere-zero Z3-flow and sign-circuit covering In 1950s, Tutte discovered that the map-coloring problem on orientable surface could be interpreted as an integer flow problem. A classic result of Tutte states that a graph with a nowhere-zero Z3-flow has a circuit cover which covers every edge at most twice, and hence has a shortest circuit cover with length at most 4/3 of the total number of edges. For an orientable graphs on non-orientable surfaces, its dual is a signed graph. In this talk, we focus on nowhere-zero Z3-flows and circuit covers of signed graphs, extending Tutte’s result from graph to signed graphs. This is based on joint work with Jiaao Li and Yezhou Wu. 18 Nov Daniel Neuen, SFU Parameterized Algorithms for Graph Isomorphism - Decompositions via Regularity In the first part of the talk, I will give an overview of recent advances on the graph isomorphism problem focusing on quasi-polynomial parameterized algorithms with a running time of the form n^{polylog(k)}, where k is some graph parameter. The first such algorithm was obtained for k being the maximum degree of the input graphs [FOCS 2018] by extending the group-theoretic tools of Babai's quasi-polynomial time isomorphism test [STOC 2016]. Subsequently, this result was generalized in a series of works to all graphs that exclude the complete graph on k vertices as a topological subgraph [SODA 2022]. In particular, this includes all graphs of Euler genus at most k-7 as well as all graphs of tree-width at most k-2.  The key concept underlying this latest algorithm is the notion of t-CR-bounded graphs that serves as a gateway to combine the group-theoretic tools underlying the isomorphism test for bounded-degree graphs with decomposition-based approaches for graphs that exclude the complete graph on k vertices as a topological subgraph. In the second part of the talk, we explore the graph-theoretic side of the algorithm in more depth and discuss how regularity of the input graphs can be leveraged to obtain decompositions into parts with few symmetries that can then be handled by the group-theoretic graph isomorphism machinery. 25 Nov Jonathan Jedwab, SFU Constructions of difference sets in groups of order $4^d$ The study of difference sets lies at the intersection of design theory, coding theory, finite geometry, and algebraic number theory. The central problem is to determine which groups contain at least one difference set, and the richest existence results occur when the group order is a power of 4. The principal obstacles are that the number of such groups grows rapidly, and that the groups have such diverse structures that an overall theory seems out of reach. However, after a ten-­year collaboration, this question was resolved completely for all 56,092 groups of order 256 using a new theoretical framework together with computational search. I shall describe the history of this problem, the methods used to resolve order 256, and the prospects for extending these techniques to order 1024.

### Spring 2022

 18 Jan  (ZOOM) Jiaxi Nie, University of California San Diego On Asymptotic Packing of Geometric Graphs A set of geometric graphs is geometric-packable if it can be asymptotically packed into every sequence of drawings of the complete graph $K_n$. For example, the set of geometric triangles is geometric-packable due to the existence of Steiner Triple Systems. When G is the 4-cycle (or 4-cycle with a chord), we show that the set of plane drawings of G is geometric-packable. In contrast, the analogous statement is false when G is nearly any other planar Hamiltonian graph (with at most 3 possible exceptions). A convex geometric graph is convex-packable if it can be asymptotically packed into the convex drawings of the complete graphs.  For each planar Hamiltonian graph G, we determine whether or not a plane G is convex-packable. Many of our proofs explicitly construct these packings; in these cases, the packings exhibit a symmetry that mirrors the vertex transitivity of $K_n$.    here is the link. (ID: 668 0051 2140, password: Graph) 25 Jan Kathryn Nurse, Simon Fraser University Toward Bouchet’s conjecture on nowhere-zero flows in signed graphs. I will present a work in progress. In 1954, Tutte proved flow-colouring duality and made a conjecture that every graph without a cut-edge has a nowhere-zero 5-flow. A parallel conjecture to this, but for signed graphs is Bouchet's conjecture (1983) that every signed graph without the obvious obstruction has a nowhere-zero 6-flow. We have been able to show that Bouchet's conjecture holds for 3-connected graphs when 6 is replaced with 8. This is joint with Matt DeVos and Robert Šámal. 01 Feb Annie Raymond (UMass) Tropicalization of graph profiles The number of homomorphisms from a graph H to a graph G, denoted by hom(H;G), is the number of maps from V(H) to V(G) that yield a graph homomorphism, i.e., that map every edge of H to an edge of G. Given a fixed collection of finite simple graphs {H_1, ..., H_s}, the graph profile is the set of all vectors (hom(H_1; G), ..., hom(H_s; G)) as G varies over all graphs.  Graph profiles essentially allow us to understand all polynomial inequalities in homomorphism numbers that are valid on all graphs. Profiles can be extremely complicated; for instance the full profile of any triple of connected graphs is not known. To simplify these objects, we introduce their tropicalization which we show is a closed convex cone that still captures interesting combinatorial information. We explicitly compute these tropicalizations for some sets of graphs, and relate the results to some questions in extremal graph theory. This is joint work with Greg Blekherman, Mohit Singh and Rekha Thomas. 08 Feb Vesna Iršič (Simon Fraser University) Winning vs. catching in the game of cops and robber on manifolds Recently, Mohar introduced a variant of the cops and robber game that is played on geodesic spaces. The game combines properties of pursuit-evasion games with the classical cops and robber game played on graphs. In the game, cops win if they can get arbitrarily close to the robber. On the other hand, cops catch the robber if one of them occupies the same point as the robber. In this talk we will discuss several strategies for players in the game, and observe the difference between the number of cops needed to catch the robber and the number of cops needed to win the game. Joint work with Bojan Mohar and Alexandra Wesolek. 15 Mar Bojan Mohar (Simon Fraser University) Proper orientations and proper chromatic number It is an interesting (and not entirely obvious) fact that every graph admits an orientation of its edges so that the outdegrees at vertices form a "coloring" (outdegrees of any two adjacent vertices are different). The proper chromatic number $\Vec{\chi}(G)$ of a graph $G$ is the minimum $k$ such that there exists an orientation of the edges of $G$ with all vertex-outdegrees at most $k$ and such that for any adjacent vertices, the outdegrees are different. Two major conjectures about the proper chromatic number are resolved. First it is shown, that $\Vec{\chi}(G)$ of any planar graph $G$ is bounded (in fact, it is at most 14). Secondly, it is shown that for every graph, $\Vec{\chi}(G)$ is at most $O(\frac{r\log r}{\log\log r})+\tfrac{1}{2}\MAD(G)$, where $r=\chi(G)$ is the usual chromatic number of the graph, and $\MAD(G)$ is the maximum average degree taken over all subgraphs of $G$. Several other related results are derived. Our proofs are based on a novel notion of fractional orientations. This is joint work with Yaobin Chen and Hehui Wu. 05 Apr Zdenek Dvorak (Charles University) 3-coloring near-quadrangulations of the plane and the torus using flows (joint work with C. Bang, E. Heath, and B. Lidicky) A graph drawn in a surface is a k-near-quadrangulation if the product of the lengths of its faces, except for 4-faces, is at most k. Near-quadrangulations play a fundamental role in the theory of 3-colorability of triangle-free graphs on surfaces.  We show how the well-known duality between colorings and flows can be used to design * a 3-precoloring extension algorithm for k-near-quadrangulations of the plane, and * a 3-coloring algorithm for k-near-quadrangulations of the torus, with time complexity polynomial in k and the number of vertices.

## 2021 Talks

### Fall 2021

 09 Nov Andrei Bulatov, Simon Fraser University The complexity of counting homomorphisms The Constraint Satisfaction Problem (CSP) provides a general framework for a wide range of combinatorial problems. The simplest way to state the problem is: Given relational structures (say, graphs) G and H, decide if there is a homomorphism from G to H. The counting version of the CSP, #CSP, asks for the number of such homomorphisms. In order to represent specific problems, the CSP is often restricted in various ways, in particular by fixing the target structure H. Thus, CSP(H) asks if, for a given structure G, there is a homomorphism from G to H. If H is a graph such a problem is often called H-Coloring. The counting versions #CSP(H), #H-Coloring of these problems are defined accordingly. In this talk we survey the developments in the study of the complexity of #CSP(H) that eventually led to a complete classification of such problems and their various generalizations.   ZOOM Information: https://sfu.zoom.us/j/66800512140?pwd=N011dU5ZNThSWnVzMFBjYnBidDdmUT09  (ID: 668 0051 2140  Password: Graph) 16 Nov Peter Bradshaw, Simon Fraser University A rainbow connectivity threshold for random graph families Given a family G of graphs on a common vertex set X, we say that G is rainbow connected if for every vertex pair u, v ∈ X, there exists a path from u to v that uses at most one edge from each graph of G. We consider the case that G contains s graphs, each sampled randomly from G(n, p), with n = |X| and p = c log n / sn , where c > 1 is a constant. We show that there exists a threshold of at most three consecutive integer values such that when s is greater than or equal to this threshold, G is a.a.s. rainbow connected, and when s is below this threshold, G is a.a.s. not rainbow connected. Joint work with Bojan Mohar.

### Summer 2021

##### Joy Morris, University of Lethbridge
Lexicographic products and wreath products
Abstract: I will present a history and overview of some of the work that has been done on the lexicographic product of graphs, and related generalisations. The focus of my talk will be on the automorphism groups of such graphs, and the relationship to the wreath product of permutation groups.
##### Xiang-dong Hou, University of South Florida
On the number of equivalence classes of boolean functions
Abstract: Two Boolean functions from $\Bbb F_2^n$ to $\Bbb F_2$ are called (affine) equivalent if one can be obtained from the other through an invertible affine transformation of the variables followed by an addition of an affine function. Most coding theoretic and cryptographic properties of Boolean functions are preserved under this equivalence. Let $N_n$ denote the number of equivalence classes of Boolean functions in $n$ variable. No explicit formula for $N_n$ is known. A long-standing open question by MacWilliams and Sloane asks for an asymptotic formula for $N_n$ as $n\to\infty$. Recently, we find a solution to this question. (Abstract in PDF)
##### Fan Chung, University of California San Diego
Trees and forests in Green's functions of a graph

Abstract: The Green's functions of a graph are the pseudo inverses of the Laplacians and therefore are useful for solving many types of Laplace equations in discrete settings.In this talk, we will give  combinatorial interpretations of Green's functions in terms of counting trees and forests in a graph. We will also mention several applications concerning the pagerank algorithms and the hitting time for random walks.

##### Akbar Rafiey, SFU
Fast and Private Submodular and k-Submodular Functions Maximization with Matroid Constraints
Abstract: The problem of maximizing nonnegative monotone submodular functions under a certain constraint has been intensively studied in the last decade, and a wide range of efficient approximation algorithms have been developed for this problem. Many machine learning problems, including data summarization and influence maximization, can be naturally modeled as the problem of maximizing monotone submodular functions. However, when such applications involve sensitive data about individuals, their privacy concerns should be addressed.
In this paper, we study the problem of maximizing monotone submodular functions subject to matroid constraints in the framework of differential privacy. We provide (1−1/e)-approximation algorithm which improves upon the previous results in terms of approximation guarantee. This is done with an almost cubic number of function evaluations in our algorithm. Moreover, we study k-submodularity, a natural generalization of submodularity. We give the first 1/2-approximation algorithm that preserves differential privacy for maximizing monotone k-submodular functions subject to matroid constraints. The approximation ratio is asymptotically tight and is obtained with an almost linear number of function evaluations.
Joint work with Yuichi Yoshida (http://proceedings.mlr.press/v119/rafiey20a.html)
##### Rebecca Patrias, University of St Thomas
Webs and tableau promotion
Abstract: We will start with an introduction to webs, standard Young tableau promotion, and the relationship between web rotation and tableau promotion. We will then discuss increasing tableaux---a K-theoretic analogue of SYT---and K-promotion. A big open question in this area deals with the order of K-promotion on increasing tableaux. We will talk about results in the 3-row case (in joint work with O. Pechenik) as well as current efforts to relate this problem to web promotion (joint with O. Pechenik, J. Striker, and J. Tymoczko).
##### Haggai Liu
Enumerative Properties of Cogrowth Series on Free products of Finite Groups
Abstract: Given a group G with a finite set of generators, S, it is natural to ask if the product of n generators from S evaluate to the identity. The enumerative version of this problem, known as the cogrowth problem, counts the number of such products and studies the associated counting sequence. Many cogrowth sequences are known. We focus on the free products of finite groups: Specifically, cyclic and dihedral groups. Such groups have the property that their cogrowth generating functions are algebraic functions, and thus, are solutions to implicit polynomial equations. Using algebraic elimination techniquesand free probability theory, we establish upper bounds on the degrees of the polynomial equations that they satisfy. This has implications for asymptotic enumeration, and makes it theoretically possible to determine the functions explicitly.
##### Christin Bibby, Louisiana State University
Combinatorics of orbit configuration spaces
Abstract: From a group action on a space, define a variant of the configuration space by insisting that no two points inhabit the same orbit. When the action is almost free, this "orbit configuration space" is the complement of an arrangement of subvarieties inside the cartesian product, and we use this structure to study its topology. We give an abstract combinatorial description of its poset of layers (connected components of intersections from the arrangement) which turns out to be of much independent interest as a generalization of partition and Dowling lattices. The close relationship to these classical posets is then exploited to give explicit cohomological calculations.
##### Yifan Jing, UIUC
Minimal and nearly minimal measure expansions in locally compact groups
Abstract: In 1964, Kemperman proved the following continuous nonabelian counterpart of the Cauchy-Davenport theorem: If G is a connected unimodular locally compact group with a left (and hence right) Haar measure \mu, A, B \subseteq G are nonempty and compact, and AB is their product set, then \mu(AB) \geq \min\{ \mu(A) + \mu(B), \mu(G)\}.
I will present the recent joint works with Jinpeng An, Chieu-Minh Tran and Ruixiang Zhang where we determine the conditions for the equality to happen or nearly happen in the above inequality. Our results and methods answer several questions by Griesmer, Henstock, Hrushovski, Kemperman, Macbeath, McCrudden, and Tao.
##### Sophie Spirkl, Waterloo
The complexity of list-5-colouring with a forbidden induced sugbraph
Abstract: A k-list-assignment for a graph G is a function L from V(G) to the set of subsets of {1,…,k}. The list-k-colouring problem asks, given G and a k-list-assignment L, is there a colouring f of G with f(v) in L(v) for all v in V(G)? This generalizes the k-colouring problem (where we use L(v)={1,…,k} for every vertex). For k at least 3, both k-colouring and list-k-colouring are NP-hard, which motivates studying the complexity of these problems when the input is restricted to H-free graphs (for a fixed H, excluded as an induced subgraph).
I will present an algorithm for list-5-colouring restricted to H-free graphs for all H which consist of connected components each of which is a 3-vertex path. This, together with previous results, gives a complete answer to the question, “for which H is list-5-colouring restricted to H-free graphs NP-hard? Joint work with Sepehr Hajebi and Yanjia Li.
##### Anurag Bishnoi, TU Delft
The minimum degree of minimal Ramsey graphs for cliques