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:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220413T163000
DTEND;TZID=Asia/Seoul:20220413T173000
DTSTAMP:20260419T112821
CREATED:20220413T073000Z
LAST-MODIFIED:20240707T080102Z
UID:5378-1649867400-1649871000@dimag.ibs.re.kr
SUMMARY:Jakub Gajarský\, Model Checking on Interpretations of Classes of Bounded Local Clique-Width
DESCRIPTION:The first-order model checking problem for finite graphs asks\, given a graph G and a first-order sentence $\phi$ as input\, to decide whether $\phi$ holds on G. Showing the existence of an efficient algorithm for this problem implies the existence of efficient parameterized algorithms for various commonly studied problems\, such as independent set\, distance-r dominating set\, and many others. \nWhile the first-order model-checking problem is likely not efficiently solvable in general\, efficient algorithms exist for various restricted graph classes\, such as graphs of bounded degree\, planar graphs etc. After the existence of an efficient model checking algorithm was shown for nowhere dense classes of graphs (which include most of commonly studied classes of sparse graphs)\, the attention turned to the more general setting of graph classes which can be obtained from sparse graphs using graph transformations called interpretations/transductions. However\, despite efforts of several groups of researchers\, no positive algorithmic result has been achieved since 2016\, when the existence of an efficient algorithm was shown for graph classes interpretable in graphs of bounded degree. \nWe present a fixed-parameter tractable algorithm for first-order model checking on interpretations of graph classes with bounded local clique-width. Notably\, this includes interpretations of planar graphs (and more generally\, of locally bounded treewidth) and vastly generalizes the result for interpretations of graphs of bounded degree. To obtain this result we developed a new tool which works in a very general setting of dependent classes and which we believe can be an important ingredient in achieving similar results in the future. \nThis is joint work with Édouard Bonnet\, Jan Dreier\, Stephan Kreutzer\, Nikolas Mählmann\, Pierre Simon\, Szymon Toruńczyk.
URL:https://dimag.ibs.re.kr/event/2022-04-13/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220427T163000
DTEND;TZID=Asia/Seoul:20220427T173000
DTSTAMP:20260419T112821
CREATED:20220427T073000Z
LAST-MODIFIED:20240705T173041Z
UID:5399-1651077000-1651080600@dimag.ibs.re.kr
SUMMARY:Michael Savery\, Induced subgraphs of induced subgraphs of large chromatic number
DESCRIPTION:We prove that for every graph F with at least one edge there are graphs H of arbitrarily large chromatic number and the same clique number as F such that every F-free induced subgraph of H has chromatic number at most c=c(F). (Here a graph is F-free if it does not contain an induced copy of F.) This generalises recent theorems of Briański\, Davies and Walczak\, and of Carbonero\, Hompe\, Moore and Spirkl. We further show an analogous statement where clique number is replaced by odd girth. This is joint work with Antonio Girão\, Freddie Illingworth\, Emil Powierski\, Alex Scott\, Youri Tamitegama and Jane Tan.
URL:https://dimag.ibs.re.kr/event/2022-04-27/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR