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

• Ilkyoo Choi (최일규), Hankuk University of Foreign Studies
• Kevin Hendrey, IBS Discrete Mathematics Group
• Pascal Gollin, IBS Discrete Mathematics Group
• Jaehoon Kim (김재훈), KAIST
• Ringi Kim (김린기), KAIST
• Seog-Jin Kim (김석진), Konkuk University
• O-joung Kwon (권오정), Incheon National University / IBS Discrete Mathematics Group
• Zi-Xia Song (宋梓霞), University of Central Florida
• Casey Tompkins, IBS Discrete Mathematics Group

Schedules

• Slot A: October 26, 2019 Saturday, 9:00am-10:15am
  1. Seog-Jin Kim
  2. Kevin Hendrey
  3. Ilkyoo Choi
• Slot B: October 26, 2019 Saturday, 10:40am-11:55pm
  1. Jaehoon Kim
  2. Ringi Kim
  3. Casey Tompkins
• Slot D: October 27, 2019 Sunday, 9:00am-10:15am
  1. Zi-Xia Song
  2. Pascal Gollin
  3. O-joung Kwon

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 $(\mathrm{\Delta }(G)+72)$-degenerate. This implies an upper bound of $\mathrm{\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 $\mathrm{\Delta }(G)$ is sufficiently large, then the upper bounds on each of these parameters of $G^2$ can all be lowered to $\mathrm{\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)>\mathrm{\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 }_{\mathrm{\Delta }}(\mathcal{G})$ for which there exist an integer $d$ such that every graph in $\mathcal{G}$ has a ${\chi }_{\mathrm{\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 $\mathrm{\Gamma }$ contains $n$ disjoint copies of $G$ as a subgraph for all $n\in \mathbb{N}$, then $\mathrm{\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 $\varphi :E(H)\to [s]$ with $e\in G_{\varphi (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)\ge 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 $\mathrm{\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\ge 1$ and graphs $G,H_1,\dots ,H_r$, we write $G\to (H_1,\dots ,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,\dots ,r\}$. A non-complete graph $G$ is $(H_1,\dots ,H_r)$-co-critical if $G\nrightarrow (H_1,\dots ,H_r)$, but $G+e\to (H_1,\dots ,H_r)$ for every edge $e$ in $\bar{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.