Oriented Coloring And Square Coloring Of Graphs

In this thesis we introduce the 2-dipath chromatic number of graphs, which combines these two concepts-oriented coloring and L(j, κ)-labelling of graphs. The 2-dipath chromatic number of some graphs and the chromatic number of square of graphs are investigated.Let (?) denote the 2-dipath chromatic number of an oriented graph (?). Let x(G~2) denote the chromatic number of square of a graph G.In Chapter 1, we collect some basic notions used in the thesis and give a chief survey on this direction. Main results in the thesis are stated.In Chapter 2, we first give some basic results and properties of 2-dipath coloring of graphs. Then we prove that every oriented Halin graph G has (?) ≤ 7 and this upper bound is tight. For instance, some oriented wheels may attain the value 7.In Chapter 3, we study the relationship between the 2-dipath chromatic number and the square chromatic number of some circular graphs. Main results are stated as follows:(1) For G(n; 1,2), G(n; 1,3) and G(n; 1,2,3), their 2-dipath chromatic numbers are equal to the chromatic number of their squares.(2) For some special integer n, the 2-dipath chromatic number of G(n; 1,4) may be less than its square chromatic number.In Chapter 4, we consider the oriented coloring problems of graphs. Given some target graphs of finite girth, we constructed the corresponding graph with given girth and study the property about homomorphism between these two graphs.