The Square Coloring, L(2,1)-Labelling And List L(2,1)-Labelling Of Graphs

Based on the study background of the frequency assignment problem, we study the square coloring, L(2, 1)-labelling and list L(2, 1)-labelling problems of graphs. Let x(G~2), λ(G), and λ_l(G) denote, respectively, the chromatic number of the square of G, the L(2, 1)-labelling number, and the list L(2,1)-labelling number of G. There are two famous conjectures about x(G2) and A(G).Conjecture 1[8] Let G be a planar graph. ThenConjecture 2[7] For any graph G with △(G) ≥ 2, we have λ(G) ≤ △2(G). However , no many results have been obtained for the parameter λ_l(G).In Chapter two, we study the square coloring problem of Halin graphs. We prove that A(G) + 1 ≤ x(G2) ≤ A(G) + 3 for any Halin graph G; and x(G2) = A(G) + 1 for any Halin graph G with △(G) ≥ 5.In Chapter three, we study the L(2, l)-labelling problem. First , we study the L(2,1)-labelling problem of Halin graphs, Mycielski graphs, and Kneser graphs, and obtain the following:(1) For any Halin graph G, we have λ(G) ≤ △(G) + 7; For any Halin graph G with △(G) ≥ 9, we have λ(G) ≤ △(G) + 2.(2) Let μ(G) be the Mycielski graph of G. For any graph G, we have λ(μ(G)) ≤ 3△(μ(G)) - 1; |G| + 1 ≤ λ(μ(G)) ≤ |G| + λ(G) + 1, both lower and upper bounds are tight; Futhermore, if |G| ≥ △2(G) + 5△(G) - 2, then λ(μ(G)) = |G| + 1; We also get the exact value of λ(μ(C_n)).