The R-hued Coloring And Distance Labeling Of Several Classes Of Graphs

Graph theory is an important branch of discrete mathematics. And the graph color-ing problems are among the important research fields in graph theory, which are widely used in science technology and engineering. Among the graph coloring problems, the r-hued coloring and distance labeling has been researched widely in recent decades, which are of important theoretical research value and application prospect.This paper mainly researched on the r-hued coloring of two types of direct product graphs and distance labeling of lexicographical product graphs and infinite triangular grid graphs. The r-hued chromatic number of two types of direct product graphs, the upper bound of L(2,1)-labeling number of lexicographical product graphs and a new lower bound of L(3,2,1)-labeling number of infinite triangular grid graphs were pre-sented. This paper included five chapters and the main points of each chapter are as follows:Chapter 1 briefly introduced the development of graph theory, research back-ground, content and preliminaries for the following chapters.Chapter 2 mainly studied the r-hued coloring of direct product graphs of paths and cycles. Many excellent results about 2-hued coloring were reported, while the results about r-hued (r≥3) coloring haven’t been reported yet. In this paper, the r-hued chromatic number of two types of direct product graphs was gained by the method of construction, contradiction and isomorphism.Chapter 3 mainly studies the L(2,1)-labeling problems of lexicographical product graphs. The famous conjecture about L(2,1)-labeling problems proposed by Griggs and Yeh hasn’t been solved thoroughly. By analyzing a L(2,1)-labeling algorithm and structure of graph, the upper bound of L(2,1)-labeling number was presented in this chapter. The correctness of conjecture proposed by Griggs and Yeh was then proved.Chapter 4 mainly studied the L(3,2,1)-labeling problems of infinite triangular grid graph. By contradiction and structure analysis, a new lower bound of L(3,2,1)-labeling number of infinite triangular grid graph was presented in this chapter, which improved the existing results.Finally, Chapter 5 presented a brief summary and prospect of this paper.