## February 2022

### James Davies, Separating polynomial $\chi$-boundedness from $\chi$-boundedness

Zoom ID: 869 4632 6610 (ibsdimag)

We prove that there is a function $f : \mathbb{N} \to \mathbb{N}$ such that for every function $g : \mathbb{N} \to \mathbb{N} \cup \{\infty\}$ with $g(1)=1$ and $g \ge f$, there is a hereditary class of graphs $\mathcal{G}$ such that for each $\omega \in \mathbb{N}$, the maximum chromatic number of a graph in $\mathcal{G}$ with

### Manuel Lafond, Recognizing k-leaf powers in polynomial time, for constant k

Zoom ID: 869 4632 6610 (ibsdimag)

A graph G is a k-leaf power if there exists a tree T whose leaf set is V(G), and such that uv is an edge if and only if the distance between u and v in T is at most k. The graph classes of k-leaf powers have several applications in computational biology, but recognizing

## March 2022

### Fedor Fomin, Long cycles in graphs: Extremal Combinatorics meets Parameterized Algorithms

Zoom ID: 869 4632 6610 (ibsdimag)

We examine algorithmic extensions of two classic results of extremal combinatorics. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree d>1, is either Hamiltonian or contains a cycle of length at least 2d. Second, the theorem of Erdős-Gallai from 1959, states that a 2-connected graph G

### Jean-Florent Raymond, Long induced paths in minor-closed graph classes and beyond

Zoom ID: 869 4632 6610 (ibsdimag)

In 1982 Galvin, Rival, and Sands proved that in $K_{t,t}$-subgraph free graphs (t being fixed), the existence of a path of order n guarantees the existence of an induced path of order f(n), for some (slowly) increasing function f. The problem of obtaining good lower-bounds for f for specific graph classes was investigated decades later

## April 2022

### Jakub Gajarský, Model Checking on Interpretations of Classes of Bounded Local Clique-Width

Zoom ID: 869 4632 6610 (ibsdimag)

The first-order model checking problem for finite graphs asks, given a graph G and a first-order sentence $\phi$ as input, to decide whether $\phi$ holds on G. Showing the existence of an efficient algorithm for this problem implies the existence of efficient parameterized algorithms for various commonly studied problems, such as independent set, distance-r dominating

### Michael Savery, Induced subgraphs of induced subgraphs of large chromatic number

Zoom ID: 869 4632 6610 (ibsdimag)

We prove that for every graph F with at least one edge there are graphs H of arbitrarily large chromatic number and the same clique number as F such that every F-free induced subgraph of H has chromatic number at most c=c(F). (Here a graph is F-free if it does not contain an induced copy

## May 2022

### Jan Kurkofka, Canonical Graph Decompositions via Coverings

Zoom ID: 869 4632 6610 (ibsdimag)

We present a canonical way to decompose finite graphs into highly connected local parts. The decomposition depends only on an integer parameter whose choice sets the intended degree of locality. The global structure of the graph, as determined by the relative position of these parts, is described by a coarser model. This is a simpler

### Sebastian Siebertz, Transducing paths in graph classes with unbounded shrubdepth

Zoom ID: 869 4632 6610 (ibsdimag)

Transductions are a general formalism for expressing transformations of graphs (and more generally, of relational structures) in logic. We prove that a graph class C can be FO-transduced from a class of bounded-height trees (that is, has bounded shrubdepth) if, and only if, from C one cannot FO-transduce the class of all paths. This establishes

## June 2022

### Jeck Lim, Sums of linear transformations

Zoom ID: 870 0312 9412 (ibsecopro)

We show that if $L_1$ and $L_2$ are linear transformations from $\mathbb{Z}^d$ to $\mathbb{Z}^d$ satisfying certain mild conditions, then, for any finite subset $A$ of $\mathbb{Z}^d$, \ This result corrects and confirms the two-summand case of a conjecture of Bukh and is best possible up to the lower-order term for many choices of $L_1$ and

### Chengfei Xie, On the packing densities of superballs in high dimensions

Zoom ID: 870 0312 9412 (ibsecopro)

The sphere packing problem asks for the densest packing of nonoverlapping equal-sized balls in the space. This is an old and difficult problem in discrete geometry. In this talk, we give a new proof for the result that for $1<p<2$, the translative packing density of superballs (a generalization of $\ell^p$ balls) in $\mathbb{R}^n$

기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209