Ken-ichi Kawarabayashi (河原林 健一), Toward Directed Graph Minor Theory

Zoom ID: 869 4632 6610 (ibsdimag)

Graph Minor project by Robertson and Seymour is perhaps the deepest theory in Graph Theory. It gives a deep structural characterization of graphs without any graph $H$ as a minor. It also gives many exciting algorithmic consequences. In this work, I would like to talk about our attempt to extend Graph minor project to directed

O-joung Kwon (권오정), Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)

Room B232 IBS (기초과학연구원)

In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying $u$ and $v$, each edge incident to exactly one of $u$ and $v$ is coloured red. Bonnet, Kim, Thomassé, and Watrigant defined the twin-width of a graph $G$ to be the minimum integer

Bo Ning (宁博), Substructures and eigenvalues of graphs: Triangles and quadrilaterals

Zoom ID: 869 4632 6610 (ibsdimag)

Our talk will mainly focus on the relationship between substructures and eigenvalues of graphs. We will briefly survey recent developments on a conjecture of Bollobás and Nikiforov and a classical result of Nosal on triangles. In particular, we shall present counting results for previous spectral theorems on triangles and quadrilaterals. If time allows, we will

Pascal Gollin, A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups

Room B232 IBS (기초과학연구원)

Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. We therefore say that cycles satisfy the Erdős-Pósa property. However, while odd cycles do not satisfy the Erdős-Pósa property, Reed proved in 1999 an analogue by

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

Jinha Kim (김진하), Independent domination of graphs with bounded maximum degree

Room B232 IBS (기초과학연구원)

An independent dominating set of a graph, also known as a maximal independent set, is a set $S$ of pairwise non-adjacent vertices such that every vertex not in $S$ is adjacent to some vertex in $S$. We prove that for $\Delta=4$ or $\Delta\ge 6$, every connected $n$-vertex graph of maximum degree at most $\Delta$ has

Donggyu Kim (김동규), A stronger version of Tutte’s wheel theorem for vertex-minors

Room B232 IBS (기초과학연구원)

Tutte (1961) proved that every simple $3$-connected graph $G$ has an edge $e$ such that $G \setminus e$ or $G / e$ is simple $3$-connected, unless $G$ is isomorphic to a wheel. We call such an edge non-essential. Oxley and Wu (2000) proved that every simple $3$-connected graph has at least $2$ non-essential edges unless

Sang-il Oum (엄상일), Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k

Room B232 IBS (기초과학연구원)

Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors, but unlike graphs, this list could be infinite in general. However, for each fixed finite field $\mathbb F$, the list contains only finitely many $\mathbb F$-representable matroids, due to the well-quasi-ordering of $\mathbb F$-representable matroids of bounded

Kevin Hendrey, A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups (revisited)

Room B232 IBS (기초과학연구원)

This talk follows on from the recent talk of Pascal Gollin in this seminar series, but will aim to be accessible for newcomers. Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. By

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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
Copyright © IBS 2018. All rights reserved.