BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv4.9.9//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;VALUE=DATE:20191026
DTEND;VALUE=DATE:20191028
DTSTAMP:20191020T190209
CREATED:20190910T133412Z
LAST-MODIFIED:20191017T004838Z
UID:1366-1572048000-1572220799@dimag.ibs.re.kr
SUMMARY:Extremal and Structural Graph Theory (2019 KMS Annual Meeting)
DESCRIPTION:Focus Session @ 2019 KMS Annual Meeting\nA 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/ \nSpeakers\n\nIlkyoo Choi (최일규)\, Hankuk University of Foreign Studies\nKevin Hendrey\, IBS Discrete Mathematics Group\nPascal Gollin\, IBS Discrete Mathematics Group\nJaehoon Kim (김재훈)\, KAIST\nRingi Kim (김린기)\, KAIST\nSeog-Jin Kim (김석진)\, Konkuk University\nO-joung Kwon (권오정)\, Incheon National University / IBS Discrete Mathematics Group\nZi-Xia Song (宋梓霞)\, University of Central Florida\nCasey Tompkins\, IBS Discrete Mathematics Group\n\nSchedules\n\nSlot A: October 26\, 2019 Saturday\, 9:00am-10:15am\n\nSeog-Jin Kim\nKevin Hendrey\nIlkyoo Choi\n\n\nSlot B: October 26\, 2019 Saturday\, 10:40am-11:55pm\n\nJaehoon Kim\nRingi Kim\nCasey Tompkins\n\n\nSlot D: October 27\, 2019 Sunday\, 9:00am-10:15am\n\nZi-Xia Song\nPascal Gollin\nO-joung Kwon\n\n\n\nAbstracts\nIlkyoo Choi (최일규)\, Degeneracy and colorings of squares of planar graphs without 4-cycles\nWe 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. \nKevin Hendrey\, Defective and clustered choosability of sparse graphs\nAn (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. \nPascal Gollin\, Progress on the Ubiquity Conjecture\nA 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. \nJaehoon Kim (김재훈)\, A rainbow version of Dirac’s theorem\nFor 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. \nRingi Kim (김린기)\, Obstructions for partitioning into forests\nFor a class $\mathcal{C}$ of graphs\, we define $\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. \nSeog-Jin Kim (김석진)\, The Alon-Tarsi number of subgraphs of a planar graph\nThis 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. \nO-joung Kwon (권오정)\, Erdős-Pósa property of H-induced subdivisions\nA 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. \nZi-Xia Song\, On the size of $(K_t\,\mathcal{T}_k)$-co-critical graphs\nGiven 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. \nCasey Tompkins\, Generalizations of the Erdős-Gallai theorem\nA 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. \n
URL:https://dimag.ibs.re.kr/event/2019-10-26/
LOCATION:Room 426\, Hong-Mun Hall\, Hongik University\, Seoul
CATEGORIES:Workshops and Conferences
END:VEVENT
END:VCALENDAR