BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//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
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20180101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;VALUE=DATE:20191026
DTEND;VALUE=DATE:20191028
DTSTAMP:20260424T075840
CREATED:20190910T133412Z
LAST-MODIFIED:20240707T090017Z
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 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. \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.
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