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;TZID=Asia/Seoul:20190508T163000
DTEND;TZID=Asia/Seoul:20190508T173000
DTSTAMP:20260423T090142
CREATED:20190310T074230Z
LAST-MODIFIED:20240707T090513Z
UID:673-1557333000-1557336600@dimag.ibs.re.kr
SUMMARY:Sang June Lee (이상준)\, On strong Sidon sets of integers
DESCRIPTION:Let $\mathbb N$ be the set of natural numbers. A set $A\subset \mathbb N$ is called a Sidon set if the sums $a_1+a_2$\, with $a_1\,a_2\in S$ and $a_1\leq a_2$\, are distinct\, or equivalently\, if \[|(x+w)-(y+z)|\geq 1\] for every $x\,y\,z\,w\in S$ with $x<y\leq z<w$. We define strong Sidon sets as follows: \nFor a constant $\alpha$ with $0\leq \alpha<1$\, a set $S\subset \mathbb N$ is called an $\alpha$-strong Sidon set if \[|(x+w)-(y+z)|\geq w^\alpha\] for every $x\,y\,z\,w\in S$ with $x<y\leq z<w$. \nThe motivation of strong Sidon sets is that a strong Sidon set generates many Sidon sets by altering each element a bit. This infers that a dense strong Sidon set will guarantee a dense Sidon set contained in a sparse random subset of $\mathbb N$. \nIn this talk\, we are interested in how dense a strong Sidon set can be. This is joint work with Yoshiharu Kohayakawa\, Carlos Gustavo Moreira and Vojtěch Rödl.
URL:https://dimag.ibs.re.kr/event/2019-05-08/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190516T163000
DTEND;TZID=Asia/Seoul:20190516T173000
DTSTAMP:20260423T090142
CREATED:20190118T041528Z
LAST-MODIFIED:20240707T090507Z
UID:423-1558024200-1558027800@dimag.ibs.re.kr
SUMMARY:Xin Zhang (张欣)\, On equitable tree-colorings of graphs
DESCRIPTION:An equitable tree-$k$-coloring of a graph is a vertex coloring using $k$ distinct colors such that every color class (i.e\, the set of vertices in a common color) induces a forest and the sizes of any two color classes differ by at most one. The minimum integer $k$ such that a graph $G$ is equitably tree-$k$-colorable is the equitable vertex arboricity of $G$\, denoted by $va_{eq}(G)$. A graph that is equitably tree-$k$-colorable may admits no equitable tree-$k’$-coloring for some $k’>k$. For example\, the complete bipartite graph $K_{9\,9}$ has an equitable tree-$2$-coloring but is not equitably tree-3-colorable. In view of this a new chromatic parameter so-called the equitable vertex arborable threshold is introduced. Precisely\, it is the minimum integer $k$ such that $G$ has an equitable tree-$k’$-coloring for any integer $k’\geq k$\, and is denoted by $va_{eq}^*(G)$. The concepts of the equitable vertex arboricity and the equitable vertex arborable threshold were introduced by J.-L. Wu\, X. Zhang and H. Li in 2013. In 2016\, X. Zhang also introduced the list analogue of the equitable tree-$k$-coloring. There are many interesting conjectures on the equitable (list) tree-colorings\, one of which\, for example\, conjectures that every graph with maximum degree at most $\Delta$ is equitably tree-$k$-colorable for any integer $k\geq (\Delta+1)/2$\, i.e\, $va_{eq}^*(G)\leq \lceil(\Delta+1)/2\rceil$. In this talk\, I review the recent progresses on the studies of the equitable tree-colorings from theoretical results to practical algorithms\, and also share some interesting problems for further research.
URL:https://dimag.ibs.re.kr/event/2019-05-16/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190520T163000
DTEND;TZID=Asia/Seoul:20190520T173000
DTSTAMP:20260423T090142
CREATED:20190304T123855Z
LAST-MODIFIED:20240707T090406Z
UID:642-1558369800-1558373400@dimag.ibs.re.kr
SUMMARY:Lars Jaffke\, A complexity dichotomy for critical values of the b-chromatic number of graphs
DESCRIPTION:A $b$-coloring of a graph $G$ is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The $b$-Coloring problem asks whether a graph $G$ has a $b$-coloring with $k$ colors.\nThe $b$-chromatic number of a graph $G$\, denoted by $\chi_b(G)$\, is the maximum number $k$ such that $G$ admits a $b$-coloring with $k$ colors. We consider the complexity of the $b$-Coloring problem\, whenever the value of $k$ is close to one of two upper bounds on $\chi_b(G)$: The maximum degree $\Delta(G)$ plus one\, and the $m$-degree\, denoted by $m(G)$\, which is defined as the maximum number $i$ such that $G$ has $i$ vertices of degree at least $i-1$. We obtain a dichotomy result stating that for fixed $k \in\{\Delta(G) + 1 − p\, m(G) − p\}$\, the problem is polynomial-time solvable whenever $p\in\{0\, 1\}$ and\, even when $k = 3$\, it is NP-complete whenever $p \ge 2$.\nWe furthermore consider parameterizations of the $b$-Coloring problem that involve the maximum degree $\Delta(G)$ of the input graph $G$ and give two FPT-algorithms. First\, we show that deciding whether a graph G has a $b$-coloring with $m(G)$ colors is FPT parameterized by $\Delta(G)$. Second\, we show that $b$-Coloring is FPT parameterized by $\Delta(G) + \ell_k(G)$\, where $\ell_k(G)$ denotes the number of vertices of degree at least $k$.\nThis is joint work with Paloma T. Lima.
URL:https://dimag.ibs.re.kr/event/2019-05-20/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR