Loading Events

« All Events

  • This event has passed.

Xin Zhang (张欣), On equitable tree-colorings of graphs

Thursday, May 16, 2019 @ 4:30 PM - 5:30 PM KST

Room B232, IBS (기초과학연구원)


Xin Zhang (张欣)
School of Mathematics and Statistics, Xidian Univeristy, China

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.


Thursday, May 16, 2019
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Room B232
IBS (기초과학연구원)


Sang-il Oum (엄상일)
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.