BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
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:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220208T163000
DTEND;TZID=Asia/Seoul:20220208T173000
DTSTAMP:20260420T134201
CREATED:20220208T073000Z
LAST-MODIFIED:20240707T080447Z
UID:5159-1644337800-1644341400@dimag.ibs.re.kr
SUMMARY:Pascal Gollin\, A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
DESCRIPTION:Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. We therefore say that cycles satisfy the Erdős-Pósa property. However\, while odd cycles do not satisfy the Erdős-Pósa property\, Reed proved in 1999 an analogue by relaxing packing to half-integral packing\, where each vertex is allowed to be contained in at most two such cycles. Moreover\, he gave a structural characterisation for when the Erdős-Pósa property for odd cycles fails. \nWe prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups\, then the cycles whose values avoid a fixed finite set for each abelian group satisfy the half-integral Erdős-Pósa property\, and we similarly give a structural characterisation for the failure of the Erdős-Pósa property. \nA multitude of natural properties of cycles can be encoded in this setting. For example\, we show that the cycles of length $\ell$ modulo $m$ satisfy the half-integral Erdős-Pósa property\, and we characterise for which values of $\ell$ and $m$ these cycles satisfy the Erdős-Pósa property. \nThis is joint work with Kevin Hendrey\, Ken-ichi Kawarabayashi\, O-joung Kwon\, Sang-il Oum\, and Youngho Yoo.
URL:https://dimag.ibs.re.kr/event/2022-02-08/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220210T163000
DTEND;TZID=Asia/Seoul:20220210T173000
DTSTAMP:20260420T134201
CREATED:20220210T073000Z
LAST-MODIFIED:20240707T080439Z
UID:5183-1644510600-1644514200@dimag.ibs.re.kr
SUMMARY:James Davies\, Separating polynomial $\chi$-boundedness from $\chi$-boundedness
DESCRIPTION:We prove that there is a function $f : \mathbb{N} \to \mathbb{N}$ such that for every function $g : \mathbb{N} \to \mathbb{N} \cup \{\infty\}$ with $g(1)=1$ and $g \ge f$\, there is a hereditary class of graphs $\mathcal{G}$ such that for each $\omega \in \mathbb{N}$\, the maximum chromatic number of a graph in $\mathcal{G}$ with clique number $\omega$ is equal to $g(\omega)$. This extends a recent breakthrough of Carbonero\, Hompe\, Moore\, and Spirk. In particular\, this proves that there are hereditary classes of graphs that are $\chi$-bounded but not polynomially $\chi$-bounded. \nJoint work with Marcin Briański and Bartosz Walczak.
URL:https://dimag.ibs.re.kr/event/2022-02-10/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220215T163000
DTEND;TZID=Asia/Seoul:20220215T173000
DTSTAMP:20260420T134201
CREATED:20220215T073000Z
LAST-MODIFIED:20240707T080430Z
UID:5212-1644942600-1644946200@dimag.ibs.re.kr
SUMMARY:Jinha Kim (김진하)\, Independent domination of graphs with bounded maximum degree
DESCRIPTION:An independent dominating set of a graph\, also known as a maximal independent set\, is a set $S$ of pairwise non-adjacent vertices such that every vertex not in $S$ is adjacent to some vertex in $S$. We prove that for $\Delta=4$ or $\Delta\ge 6$\, every connected $n$-vertex graph of maximum degree at most $\Delta$ has an independent dominating set of size at most $(1-\frac{\Delta}{ \lfloor\Delta^2/4\rfloor+\Delta })(n-1)+1$. In addition\, we characterize all connected graphs having the equality and we show that other connected graphs have an independent dominating set of size at most $(1-\frac{\Delta}{ \lfloor\Delta^2/4\rfloor+\Delta })n$.\nThis is joint work with Eun-Kyung Cho\, Minki Kim\, and Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2022-02-15/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220218T100000
DTEND;TZID=Asia/Seoul:20220218T110000
DTSTAMP:20260420T134201
CREATED:20220218T010000Z
LAST-MODIFIED:20240705T174212Z
UID:5154-1645178400-1645182000@dimag.ibs.re.kr
SUMMARY:Manuel Lafond\, Recognizing k-leaf powers in polynomial time\, for constant k
DESCRIPTION:A graph G is a k-leaf power if there exists a tree T whose leaf set is V(G)\, and such that uv is an edge if and only if the distance between u and v in T is at most k. The graph classes of k-leaf powers have several applications in computational biology\, but recognizing them has remained a challenging algorithmic problem for the past two decades. In a recent paper presented at SODA22\, it was shown that k-leaf powers can be recognized in polynomial time if k is fixed. \nIn this seminar\, I will present the algorithm that decides whether a graph G is a k-leaf power in time $O(n^{f(k)})$ for some function f that depends only on k (but has the growth rate of a power tower function). More specifically\, I will discuss how the difficult k-leaf power instances contain many cutsets that have the same neighborhood layering. I will then show that these similar cutsets are redundant and that removing one of them does not lose any information\, which can be exploited for algorithmic purposes.
URL:https://dimag.ibs.re.kr/event/2022-02-18/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220221T163000
DTEND;TZID=Asia/Seoul:20220221T173000
DTSTAMP:20260420T134201
CREATED:20220221T073000Z
LAST-MODIFIED:20240707T080414Z
UID:5216-1645461000-1645464600@dimag.ibs.re.kr
SUMMARY:Donggyu Kim (김동규)\, A stronger version of Tutte's wheel theorem for vertex-minors
DESCRIPTION:Tutte (1961) proved that every simple $3$-connected graph $G$ has an edge $e$ such that $G \setminus e$ or $G / e$ is simple $3$-connected\, unless $G$ is isomorphic to a wheel. We call such an edge non-essential. Oxley and Wu (2000) proved that every simple $3$-connected graph has at least $2$ non-essential edges unless it is isomorphic to a wheel. Moreover\, they proved that every simple $3$-connected graph has at least $3$ non-essential edges if and only if it is isomorphic to neither a twisted wheel nor a $k$-dimensional wheel with $k\geq2$. \nWe prove analogous results for graphs with vertex-minors. For a vertex $v$ of a graph $G$\, let $G*v$ be the graph obtained from $G$ by deleting all edges joining two neighbors of $v$ and adding edges joining non-adjacent pairs of two neighbors of $v$. This operation is called the local complementation at $v$\, and we say two graphs are locally equivalent if one can be obtained from the other by applying a sequence of local complementations. A graph $H$ is a vertex-minor of a graph $G$ if $H$ is an induced subgraph of a graph locally equivalent to $G$. A split of a graph is a partition $(A\,B)$ of its vertex set such that $|A|\,|B| \geq 2$ and for some $A’\subseteq A$ and $B’\subseteq B$\, two vertices $x\in A$ and $y\in B$ are adjacent if and only if $x\in A’$ and $y\in B’$. A graph is prime if it has no split. \nA vertex $v$ of a graph is non-essential if at least two of three kinds of vertex-minor reductions at $v$ result in prime graphs. We prove that every prime graph with at least $5$ vertices has at least two non-essential vertices unless it is locally equivalent to a cycle. It is stronger than a theorem proved by Allys (1994)\, which states that every prime graph with at least $5$ vertices has a non-essential vertex unless it is locally equivalent to a cycle. As a corollary of our result\, one can obtain the first result of Oxley and Wu. Furthermore\, we show that every prime graph with at least $5$ vertices has at least $3$ non-essential vertices if and only if it is not locally equivalent to a graph with two specified vertices $x$ and $y$ consisting of at least two internally-disjoint paths from $x$ to $y$ in which $x$ and $y$ have no common neighbor. \nThis is joint work with Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2022-02-21/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220228T163000
DTEND;TZID=Asia/Seoul:20220228T173000
DTSTAMP:20260420T134201
CREATED:20220228T073000Z
LAST-MODIFIED:20240707T080351Z
UID:5298-1646065800-1646069400@dimag.ibs.re.kr
SUMMARY:Sang-il Oum (엄상일)\, Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k
DESCRIPTION:Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors\, but unlike graphs\, this list could be infinite in general. However\, for each fixed finite field $\mathbb F$\, the list contains only finitely many $\mathbb F$-representable matroids\, due to the well-quasi-ordering of $\mathbb F$-representable matroids of bounded branch-width under taking matroid minors [J. F. Geelen\, A. M. H. Gerards\, and G. Whittle (2002)]. But this proof is non-constructive and does not provide any algorithm for computing these $\mathbb F$-representable excluded minors in general. \nWe consider the class of matroids of path-width at most $k$ for fixed $k$. We prove that for a finite field $\mathbb F$\, every $\mathbb F$-representable excluded minor for the class of matroids of path-width at most~$k$ has at most $2^{|\mathbb{F}|^{O(k^2)}}$ elements. We can therefore compute\, for any integer $k$ and a fixed finite field $\mathbb F$\, the set of $\mathbb F$-representable excluded minors for the class of matroids of path-width $k$\, and this gives as a corollary a polynomial-time algorithm for checking whether the path-width of an $\mathbb F$-represented matroid is at most $k$. We also prove that every excluded pivot-minor for the class of graphs having linear rank-width at most $k$ has at most $2^{2^{O(k^2)}}$ vertices\, which also results in a similar algorithmic consequence for linear rank-width of graphs. \nThis is joint work with Mamadou M. Kanté\, Eun Jung Kim\, and O-joung Kwon.
URL:https://dimag.ibs.re.kr/event/2022-02-28/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR