2010

Ph.D

HBNI

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 a proper coloring is required such that the union of any two color classes is acyclic. Other well studied 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. The upper bounds for forbidden subgraph chromatic numbers is found in terms of the maximum degree. For the union of two color classes, and it is shown that the asymptotic tightness of our bounds by a probabilistic contstruction. And that the oriented chromatic number of a graph can be bounded in terms of the forbidden subgraph chromatic numbers. In conjunction with afore-mentioned results, this allowed the author to prove improved bounds on oriented chromatic numbers of graphs on surfaces.