Research On Queue Numbers And General Chromatic Numbers And Their Applications

Queues are fundamental data structures in computer science.In 1992,Heath,Leighton and Rosenberg first extended the data structure of queue to graph theory,and gave the concepts of queue-number.Then in 2005,Wood introduced the definition of strict queues.Rainbows and weak rainbows are dual definitions of queues and strict queues respectively.Wood applied the strong product structure to the queue-number in 2005.For the k-th power graphs,Wood gave the upper and lower bounds of the queue-number and the strict-queue-number for the k-th power graph of path and cycle.For a long time,whether a planar graph has a bounded queue-number has been a very important problem.This problem was solved by Dujmovic,Joret,Micek,Morin,Ueckerdt and Wood in 2019,and its upper bound is 49.Alon,Grytzuk,Haluszczak and Rlordan combined the idea of non-repeated sequences with graph coloring in graph theory,and introduced the definition of non-repetitive colouring of graphs in 2002.In 2003,Kierstead and Daqing Yang introduced the definition of general colouring number.These definitions have been widely concerned in graph theory,and are very hot topics.This dissertation focuses on the above concepts.The dissertation is divided into four chapters,as follows:In Chapter 1,we first collect some basic notations that will be used frequently throughout the thesis.Then we present a chief survey in this direction and later we state the main results obtained.In Chapter 2,we first study the product structure of the k-th power of trees,and give two kinds of product structures for the k-th power of trees.Then,with the application of the product structure to queue-number and non-repetitive chromatic number,we give some upper bounds for queue-number and non-repetitive chromatic number for the k-th power of trees.Considering the lower bound of its non-repetitive chromatic number,we find that the upper bound is asymptotically tight for any given k.In Chapter 3,by applying the dual relationship between the queues and rainbows,and the dual relationship between the strict-queues and weak rainbows,we improves the upper bound of the queue-number and the strict-queue-number of the k-th power of trees.Considering the lower bounds of its queue-number and strict-queue-number,we find that the upper bound of queue-number and strict-queue-number is asymptotically tight.In Chapter 4,we study the general colouring number of the line graphs of trees and k-trees,and give the upper bound of the general colouring number for the line graphs of trees and k-trees by applying the relation between the vertex ordering of the line graphs and the edge ordering of the original graphs.