기초과학연구원 이산수학그룹
The square of a graph $G$, denoted $G^2$, has the same vertex set as $G$ and has an edge between two vertices if the distance between them in $G$ is at most $2$. Wegner's conjecture (1977) states that for a planar graph $G$, the chromatic number $\chi(G^2)$ of $G^2$ is at most 7 if $\Delta(G) …
Even delta-matroids generalize matroids, as they are defined by a certain basis exchange axiom weaker than that of matroids. One natural example of even delta-matroids comes from a skew-symmetric matrix over a given field $K$, and we say such an even delta-matroid is representable over the field $K$. Interestingly, a matroid is representable over $K$ …
Graph pebbling is a combinatorial game played on an undirected graph with an initial configuration of pebbles. A pebbling move consists of removing two pebbles from one vertex and placing one pebbling on an adjacent vertex. The pebbling number of a graph is the smallest number of pebbles necessary such that, given any initial configuration …
The k-color induced size-Ramsey number of a graph H is the smallest number of edges a (host) graph G can have such that for any k-coloring of its edges, there exists a monochromatic copy of H which is an induced subgraph of G. In 1995, in their seminal paper, Haxell, Kohayakawa and Łuczak showed that …
This workshop aims to foster collaborative discussions and explore the various aspects of vertex-minors, including structural theory and their applications. This event will be small-scale, allowing for focused talks and meaningful interactions among participants. Website: https://indico.ibs.re.kr/event/596/
An edge-coloured graph is said to be rainbow if it uses no colour more than once. Extremal problems involving rainbow objects have been a focus of much research over the last decade as they capture the essence of a number of interesting problems in a variety of areas. A particularly intensively studied question due to …
Graph product structure theory describes complex graphs in terms of products of simpler graphs. In this talk, I will introduce this subject and talk about some of my recent results in this area. The focus of my talk will be on a new tool in graph product structure theory called `blocking partitions.’ I’ll show how …
We prove that every finite colouring of the plane contains a monochromatic pair of points at an odd integral distance from each other.
The 3rd East Asia Workshop on Extremal and Structural Graph Theory is a workshop to bring active researchers in the field of extremal and structural graph theory, especially in the East Asia such as China, Japan, and Korea. Website: http://tgt.ynu.ac.jp/2023EastAsia.html
Determining the density required to ensure that a host graph G contains some target graph as a subgraph or minor is a natural and well-studied question in extremal combinatorics. The celebrated 50-year-old Erdős-Sós conjecture states that for every k, if G has average degree exceeding k-2 then it contains every tree T with k vertices …