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:20180101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190516T163000
DTEND;TZID=Asia/Seoul:20190516T173000
DTSTAMP:20260423T105907
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
END:VCALENDAR