Loading Events

« All Events

  • This event has passed.
:

Xin Zhang (张欣), On the equitable tree-coloring of graphs with low degeneracy

February 25 Tuesday @ 4:30 PM - 5:30 PM KST

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

Speaker

Xin Zhang (张欣)
School of Mathematics and Statistics, Xidian Univeristy, China
https://faculty.xidian.edu.cn/zhangxin/en

A (vertex) $k$-coloring of a graph $G$ is a tree-coloring if each color class induces a forest, and is equitable if the sizes of any two color classes differ by at most 1. The first relative result concerning the equitable tree-coloring of graphs is due to H. Fan, H. A. Kierstead, G. Liu, T. Molla, J.-L. Wu, and X. Zhang (2011), who proved that any graph with maximum degree at most $\Delta$ has a $\Delta$-coloring so that each color class induces a graph with maximum degree at most 1. After that, many results on this topic were published in the literature. For example, L. Esperet, L. Lemoine, and F. Maffray (2015) showed that any planar graph admits an equitable tree-$k$-coloring for every integer $k\ge 4$,and G. Chen, Y. Gao, S. Shan, G. Wang, and J.-L. Wu (2017) proved that any 5-degenerate graph with maximum degree at most $\Delta$ admits an equitable tree-$k$-coloring for every $k\geq \lceil\frac{\Delta+1}{2}\rceil$.

In this talk, we review part of the known results and the conjectures on the equitable tree-coloring of graphs, and then show the sketch proofs of our three new results as follows:

(a) the vertex set of any graph $G$ can be equitably partitioned into $k$ subsets for any integer $k\geq\max\{\lceil\frac{\Delta(G)+1}{2}\rceil,\lceil\frac{|G|}{4}\rceil\}$ so that each of them induces a linear forest;

(b) any plane graph with independent crossings admits an equitable tree-$k$-coloring for every integer $k\ge 8$;

(c) any $d$-degenerate graph with maximum degree at most $\Delta$ admits an equitable tree-$k$-coloring for every integer $k\geq (\Delta+1)/2$ provided that $\Delta\geq 10d$.

This is a joint work with Yuping Gao, Bi Li, Yan Li, and Bei Niu.

Details

Date:
February 25 Tuesday
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Venue

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

Organizer

Sang-il Oum (엄상일)
Website:
https://dimag.ibs.re.kr/home/sangil/
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.