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:20200721T163000
DTEND;TZID=Asia/Seoul:20200721T173000
DTSTAMP:20260420T031106
CREATED:20200519T123058Z
LAST-MODIFIED:20240707T083754Z
UID:2456-1595349000-1595352600@dimag.ibs.re.kr
SUMMARY:Ilkyoo Choi (최일규)\, Flexibility of Planar Graphs
DESCRIPTION:Oftentimes in chromatic graph theory\, precoloring techniques are utilized in order to obtain the desired coloring result. For example\, Thomassen’s proof for 5-choosability of planar graphs actually shows that two adjacent vertices on the same face can be precolored. In this vein\, we investigate a precoloring extension problem formalized by Dvorak\, Norin\, and Postle named flexibility. Given a list assignment $L$ on a graph $G$\, an $L$-request is a function on a subset $S$ of the vertices that indicates a preferred color in $L(v)$ for each vertex $v\in S$. A graph $G$ is $\varepsilon$-flexible for list size $k$ if given a $k$-list assignment $L$ and an $L$-request\, there is an $L$-coloring of $G$ satisfying an $\varepsilon$-fraction of the requests in $S$. We survey known results regarding this new concept\, and prove some new results regarding flexibility of planar graphs.
URL:https://dimag.ibs.re.kr/event/2020-07-21/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR