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:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200303T163000
DTEND;TZID=Asia/Seoul:20200303T173000
DTSTAMP:20260420T095415
CREATED:20200207T093644Z
LAST-MODIFIED:20240707T091837Z
UID:2099-1583253000-1583256600@dimag.ibs.re.kr
SUMMARY:Eun-Kyung Cho (조은경)\, Decomposition of a planar graph into a $d$-degenerate graph and a graph with maximum degree at most $h$
DESCRIPTION:Given a graph $G$\, a decomposition of $G$ is a collection of spanning subgraphs $H_1\, \ldots\, H_t$ of $G$ such that each edge of $G$ is an edge of $H_i$ for exactly one $i \in \{1\, \ldots\, t\}$. Given a positive integer $d$\, a graph is said to be $d$-degenerate if every subgraph of it has a vertex of degree at most $d$. Given a non-negative integer $h$\, we say that a graph $G$ is $(d\,h)$-decomposable if there is a decomposition of $G$ into two spanning subgraphs\, where one is a $d$-degenerate graph\, and the other is a graph with maximum degree at most $h$. \nIt is known that a planar graph is $5$-degenerate\, but not always $4$-degenerate. This implies that a planar graph is $(5\,0)$-decomposable\, but not always $(4\,0)$-decomposable. Moreover\, by related previous results\, it is known that a planar graph is $(3\,4)$- and $(2\,8)$-decomposable. \nIn this talk\, we improve these results by showing that every planar graph is $(4\,1)$-\, $(3\,2)$-\, and $(2\,6)$-decomposable. The $(4\,1)$- and $(3\,2)$-decomposabilities are sharp in the sense that the maximum degree condition cannot be reduced more. \nThis is joint work with Ilkyoo Choi\, Ringi Kim\, Boram Park\, Tingting Shan\, and Xuding Zhu.
URL:https://dimag.ibs.re.kr/event/2020-03-03/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR