Forbidden subgraph colorings, oriented colorings and intersection dimensions of graphs

Abstract

This thesis deals mainly with two related coloring problems ? forbidden subgraph colorings and oriented colorings. The former deals with proper colorings of vertices or edges of a graph with constraints on the union of color classes. A well-known example is the acyclic vertex coloring in which we require a proper coloring such that the union of any two color classes is acyclic. Other wellstudied examples include the acyclic edge coloring and star coloring. Our focus in this thesis is a generalization of these special types of colorings. Oriented coloring deals with colorings of oriented graphs (directed graphs obtained by orienting each edge of a simple undirected graph). Specifically, an oriented coloring is a homomorphism to an oriented graph, the vertices of the target graph being considered as the colors assigned to the vertices of the source graph. For both of these problems, we want to find good upper bounds for the number of colors required for such colorings. In this thesis, we find upper bounds for forbidden subgraph chromatic numbers in terms of the maximum degree. For the union of two color classes, we show the asymptotic tightness of our bounds by a probabilistic contstruction. We then show that the oriented chromatic number of a graph can be bounded in terms of the forbidden subgraph chromatic numbers. In conjunction with our afore-mentioned results, this allowed us to prove improved bounds on oriented chromatic numbers of graphs on surfaces. Specifically, we obtained the following results: ? Given a family F of connected graphs each having at least m edges, the vertices of any graph ofmaximum degree _ can be properly colored using O(_1+ 1 mand#8722;1 ) colors so that in the union of any 2 color classes, there is no copy of H for any H and#8712; F. ? Any graph of genus g has oriented chromatic number at most 2g1/2+o(1) . We also consider edge colorings of graphs with restrictions on the union of color classes. While edge colorings can simply be considered as vertex colorings of the line graph.