2021/03/08 by Jiaqi Wang, Daqing Yang, Wang, Jiaqi +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2103.04670
Dujmović, Joret, Micek, Morin, Ueckerdt and Wood recently in [Planar graphs have bounded queue-number, Journal of the ACM, Volume 67, Issue 4, Article No.: 22, August 2020] showed some attractive graph product structure theorems for planar graphs. By using the product structure, they proved that planar graphs have bounded queue-number 48; in [Planar graphs have bounded nonrepetitive chromatic number, Advances in Combinatorics, 5, 11 pp, 2020], the authors proved that planar graphs have bounded nonrepetitive chromatic number 768. In this paper, still by using some product structure theorem, we improve the upper bound of queue-number of planar graphs to 27 and the non-repetitive chromatic number to 320. We also study powers of trees. We show a graph product structure theorem of the k-th power Tk of tree T, then use it giving an upper bound of the nonrepetitive~chromatic~number of Tk. We also give an asymptotically tight upper bound of the queue-number of Tk.