Loading Events

« All Events

:

Extremal and Structural Graph Theory (2019 KMS Annual Meeting)

October 26 Saturday - October 27 Sunday

Hong-Mun Hall, Hongik University, Seoul

Focus Session @ 2019 KMS Annual Meeting

A focus session “Extremal and Structural Graph Theory” at the 2019 KMS Annual Meeting is organized by Sang-il Oum.

URL: http://www.kms.or.kr/meetings/fall2019/

Speakers

Abstracts

Ilkyoo Choi (최일규), Degeneracy and colorings of squares of planar graphs without 4-cycles

We prove several results on coloring squares of planar graphs without 4-cycles. First, we show that if $G$ is such a graph, then $G^2$ is $(\Delta(G)+72)$-degenerate. This implies an upper bound of $\Delta(G)+73$ on the chromatic number of $G^2$ as well as on several variants of the chromatic number such as the list-chromatic number, paint number, Alon–Tarsi number, and correspondence chromatic number. We also show that if $\Delta(G)$ is sufficiently large, then the upper bounds on each of these parameters of $G^2$ can all be lowered to $\Delta(G)+2$ (which is best possible). To complement these results, we show that 4-cycles are unique in having this property. Specifically, let $S$ be a finite list of positive integers, with $4\notin S$. For each constant $C$, we construct a planar graph $G_{S,C}$ with no cycle with length in $S$, but for which $\chi(G_{S,C}^2) > \Delta(G_{S,C})+C$. This is joint work with Dan Cranston and Theo Pierron.

Kevin Hendrey, Defective and clustered choosability of sparse graphs

An (improper) graph colouring has defect $d$ if each monochromatic subgraph has maximum degree at most $d$, and has clustering $c$ if each monochromatic component has at most $c$ vertices. Given an infinite class of graphs $\mathcal{G}$, it is interesting to ask for the minimum integer $\chi_{\Delta}(\mathcal{G})$ for which there exist an integer $d$ such that every graph in $\mathcal{G}$ has a $\chi_{\Delta}(\mathcal{G})$-colouring with defect at most $d$, and the minimum integer $\chi_{\star}(\mathcal{G})$-colouring for which there exist an integer $c$ such that every graph in $\mathcal{G}$ has a $\chi_{\star}(\mathcal{G})$-colouring with clustering at most $c$. We explore clustered and defective colouring in graph classes with bounded maximum average degree. As an example, our results show that every earth-moon graph has an 8-colouring with clustering at most 405. Our results hold in the stronger setting of list-colouring. Joint work with David Wood.

Pascal Gollin, Progress on the Ubiquity Conjecture

A classic result of Halin says that if a graph $G$ contains for every $n \in \mathbb{N}$ as subgraphs $n$ disjoint rays, i.e., one-way infinite paths, then $G$ already contains infinitely many disjoint rays as subgraphs.

We say a graph $G$ is ubiquitous with respect to the subgraph relation if whenever a graph $\Gamma$ contains $n$ disjoint copies of $G$ as a subgraph for all $n \in \mathbb{N}$, then $\Gamma$ already contains infinitely many disjoint copies of $G$ as a subgraph. We define ubiquity w.r.t. the minor relation or topological minor relation analogously.

A fundamental conjecture about infinite graphs due to Andreae is the Ubiquity Conjecture. It states that every locally finite connected graph is ubiquitous w.r.t. the minor relation.

In a series of papers we make progress on the conjecture proving various ubiquity results w.r.t. both the topological minor relation and the minor relation, making use of well-quasi ordering techniques.

Jaehoon Kim (김재훈), A rainbow version of Dirac’s theorem

For a collection $\mathbf{G}=\{G_1,\dots, G_s\}$ of graphs, we say that a graph $H$ is $\mathbf{G}$-transversal, or $\mathbf{G}$-rainbow, if there exists a bijection $\phi:E(H)\rightarrow [s]$ with $e\in G_{\phi(e)}$ for all $e\in E(H)$.

Aharoni conjectured that if for each $i\in [r]$, then graph $G_i$ is an $n$-vertex graph on the same vertex set $V$ and $\delta(G_i)\geq n/2$ for all $i\in [s]$, then there exists a $\mathbf{G}$-transversal Hamilton cycle on $V$. We prove this conjecture. We also prove a similar result for $K_r$-factors. This is joint work with Felix Joos.

Ringi Kim (김린기), Obstructions for partitioning into forests

For a class $\mathcal{C}$ of graphs, we de fine $\mathcal{C}$-edge-brittleness of a graph $G$ as the minimum $\ell$ such that the vertex set of $G$ can be partitioned into sets inducing a subgraph in $\mathcal{C}$ and there are $\ell$ edges having ends in distinct parts. 

In this talk, we characterize classes of graphs having bounded $\mathcal{C}$-edge-brittleness for a class $\mathcal{C}$ of forests in terms of forbidden obstructions. This is joint work with Sang-il Oum and Sergey Norin.

Seog-Jin Kim (김석진), The Alon-Tarsi number of subgraphs of a planar graph

This paper constructs a planar graph $G_1$ such that for any subgraph $H$ of $G_1$ with maximum degree $\Delta(H) \le 3$, $G_1-E(H)$ is not $3$-choosable, and a planar graph $G_2$ such that for any star forest $F$ in $G_2$, $G_2-E(F)$ contains a copy of $K_4$ and hence $G_2-E(F)$ is not $3$-colourable. On the other hand, we prove that every planar graph $G$ contains a forest $F$ such that the Alon-Tarsi number of $G – E(F)$ is at most $3$, and hence $G – E(F)$ is 3-paintable and 3-choosable. This is joint work with Ringi Kim and Xuding Zhu.

O-joung Kwon (권오정), Erdős-Pósa property of H-induced subdivisions

A class $\mathcal{F}$ of graphs has the induced Erdős-Pósa property if there exists a function $f$ such that for every graph $G$ and every positive integer $k$, $G$ contains either $k$ pairwise vertex-disjoint induced subgraphs that belong to $\mathcal{F}$, or a vertex set of size at most $f(k)$ hitting all induced copies of graphs in $\mathcal{F}$. Kim and Kwon (SODA’18) showed that for a cycle $C_{\ell}$ of length $\ell$, the class of $C_{\ell}$-subdivisions has the induced Erdős-Pósa property if and only if $\ell\le 4$. In this paper, we investigate whether or not the class of $H$-subdivisions has the induced Erdős-Pósa property for other graphs $H$.

We completely settle the case when $H$ is a forest or a complete bipartite graph. Regarding the general case, we identify necessary conditions on $H$ for the class of $H$-subdivisions to have the induced Erdős-Pósa property. For this, we provide three basic constructions that are useful to prove that the class of the subdivisions of a graph does not have the induced Erdős-Pósa property. Among remaining graphs, we prove that if $H$ is either the diamond, the $1$-pan, or the $2$-pan, then the class of $H$-subdivisions has the induced Erdős-Pósa property.

Zi-Xia Song, On the size of $(K_t,\mathcal{T}_k)$-co-critical graphs

Given an integer $r\ge1$ and graphs $G, H_1, \ldots, H_r$, we write $G \rightarrow ({H}_1, \ldots, {H}_r)$ if every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H_i$ in color $i$ for some $i\in\{1, \ldots, r\}$. A non-complete graph $G$ is $(H_1, \ldots, H_r)$-co-critical if $G \nrightarrow ({H}_1, \ldots, {H}_r)$, but $G+e\rightarrow ({H}_1, \ldots, {H}_r)$ for every edge $e$ in $\overline{G}$. Motivated by Hanson and Toft’s conjecture, we study the minimum number of edges over all $(K_t, \mathcal{T}_k)$-co-critical graphs on $n$ vertices, where $\mathcal{T}_k$ denotes the family of all trees on $k$ vertices. In this talk, we will present our recent results on this topic.

This is joint work with Jingmei Zhang. 

Casey Tompkins, Generalizations of the Erdős-Gallai theorem

A classical result of Erdős and Gallai bounds the number of edges in an $n$-vertex graph with no path of length $k$ (denoted $P_k$). In this talk, I will discuss generalizations of this result in multiple settings. In one direction, I will consider so-called generalized Turán problems for $P_k$-free graphs. That is, rather than maximizing the number of edges, we consider maximizing the number of copies of some graph $H$. Building on results of Luo where $H$ is a clique, we consider the case when $H$ is also a path.

In another direction, I will consider Erdős-Gallai type problems in a hypergraph setting. Here I will discuss recent results involving forbidding Berge copies of a path, including the solution to some problems and conjectures of Győri, Katona and Lemons as well Füredi, Kostochka and Luo. I will also mention some Kopylov-type variants of this problem where the hypergraph is assumed to be connected. Moreover, I will discuss some recent work on forbidding Berge copies of a tree. Finally, as time permits I will mention some colored variants of the Erdős-Gallai problem. 

The new results presented are joint work with various subsets of the authors Akbar Davoodi, Beka Ergemlidze, Ervin Győri, Abhishek Methuku, Nika Salia, Mate Vizer, Oscar Zamora.

Details

Start:
October 26 Saturday
End:
October 27 Sunday
Event Category:

Venue

Hong-Mun Hall, Hongik University, Seoul

Organizer

Sang-il Oum