张欣副教授新葡的京集团8814

报告题目：On equitable tree-colorings of graphs

报告人: 张欣 副教授 （西安电子科技大学）

报告时间: 2019年6月27日10:00

报告地点: 数学院大会议室341

内容摘要： An equitable tree-$k$-coloring of a graph is a vertex coloring using $k$ distinct colors such that every color class 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.

报告人简介: 张欣，2007年7月毕业于山东大学数学与系统科学学院，获得理学学士学位，同年9月，进入山东大学数学学院攻读博士学位，师从吴建良教授（硕士阶段）与刘桂真教授（博士阶段），于2012年6月毕业并获得理学博士学位，现任西安电子科技大学数学与统计学院副教授、硕士研究生导师，主要从事图论及其应用方向的科研教学工作，研究兴趣包括图（网络）的拓扑结构与染色（划分），信息编码理论等，现发表SCI检索学术论文60余篇，主持国家自然科学基金面上基金项目与青年科学基金项目各一项，高等学校博士学科点专项科研基金一项，陕西省自然科学基础研究计划面上项目与青年人才项目各一项，入选西安市科协青年人才托举计划，曾获得山东省优秀博士学位论文奖，陕西高等学校科学技术奖二等奖，中国运筹学会青年科技奖等多项科研奖励，现为《Journal of Combinatorial Theory, Series B》、《Journal of Graph Theory》、《Discrete Applied Mathematics》、《Discrete Mathematics》、《Graphs and Combinatorics》、《数学学报（英文版）》等国际期刊的审稿人，美国数学会《Mathematical Reviews》评论员，中国运筹学会图论组合分会青年理事，中国工业与应用数学学会图论组合及应用专业委员会委员。