Forbidden subgraph colorings, Oriented colorings and intersection dimensions of graphs[HBNI Th 32]

DSpace/Manakin Repository

Forbidden subgraph colorings, Oriented colorings and intersection dimensions of graphs[HBNI Th 32]

Show simple item record

dc.contributor.author Aravind, N. R.
dc.date.accessioned 2011-08-25T10:22:49Z
dc.date.available 2011-08-25T10:22:49Z
dc.date.issued 2011-08-25T10:22:49Z
dc.date.submitted 2010
dc.identifier.uri http://hdl.handle.net/123456789/258
dc.description.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 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. en_US
dc.subject Graph Colorings en_US
dc.subject HBNI Th 32 en_US
dc.title Forbidden subgraph colorings, Oriented colorings and intersection dimensions of graphs[HBNI Th 32] en_US
dc.type.degree Ph.D en_US
dc.type.institution HBNI en_US
dc.description.advisor Subramanian, C.R.
dc.description.advisor Balasubramanian, R.
dc.description.pages 101p. en_US
dc.type.mainsub Computer Science en_US

Files in this item

Files Size Format View
NR Aravind.pdf 775.8Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account