Coloring of metric spaces and L(2,1)-labeling of graphs

This thesis focuses on topics in combinatorial geometry and extremal graph theory. It contains results on coloring of geometric structures and graph coloring extensions.;We consider coloring of n-space under different metrics. We investigate c&parl0;Rnp ,1&parr0; , the chromatic number of the unit distance graph on Rn under the ℓp-norm. We prove that c&parl0;Rnp ,1&parr0; is bounded above by p/2pn &parl0;5ep1/p&parr0; n , 9n, and c( n ln n)5n, and below by (1.139)n.;For the discrete case c&parl0;Zn 1,r&parr0; , the same exponential lower and upper bounds of c&parl0;Rnp ,1&parr0; hold when r is large. We also prove various bounds that are better when r, n are small: &parl0;Zn1 ,r&parr0; is bipartite when r is odd, c&parl0;Zn 1,2&parr0; = 2n for all n, but c&parl0;Zn 1,r&parr0; ≥ 2n + 1 for n ≥ 3 and even r ≥ 4, and a recursive upper bound 3rn -2.;The third upper bound c(n ln n)5n on c&parl0;Rnp ,1&parr0; , mentioned above, uses a special covering of Rn with convex bodies. In 1962, Erdo&huml;s and Rogers showed that, for sufficiently large n, there exists a covering of Rn by translates of a given convex body with multiplicity at most cn ln n for absolute constant c. In this thesis, we give a new combinatorial proof of this covering result using methods from probabilistic combinatorics and discrete geometry.;Finally, we study the L(2, 1)-labeling problem for graphs. A nonnegative-integer coloring f on V( G) is an L(2, 1)-labeling if | f(u) - f(v)| ≥ 2 for each edge uv and |f(u) - f(v)| ≥ 1 for each pair u, v at distance 2. This extends the usual notion of graph coloring. We seek a parameter lambda(G) that is the smallest number t such that G has an L(2, 1)-labeling using labels ≤ t.;Griggs and Yeh [1992] conjectured that always lambda(G) ≤ Delta 2(G). We prove this conjecture for 3-regular Hamiltonian graphs.;We also show that lambda(G) = q 2 + q = Delta2 - Delta for the incidence graph G of the projective plane PG (2, q). To prove this result, we convert the problem to a problem of packing of bipartite graphs into a complete bipartite graph. We also bound lambda(G) when G is the Kneser graph K(2k + 1, k).