Please use this identifier to cite or link to this item: http://hdl.handle.net/10603/4726
Title: Forbidden subgraph colorings, oriented colorings and intersection dimensions of graphs
Researcher: Arvind, N R
Guide(s): Balasubramanian R
Subramanian, C R
Keywords: Graphs
Graphs dimensions
Graphs colorings
Upload Date: 17-Sep-2012
University: Homi Bhabha National Institute
Completed Date: July, 2010
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.
Pagination: 101p.
URI: http://hdl.handle.net/10603/4726
Appears in Departments:Department of Mathematical Sciences

Files in This Item:
File Description SizeFormat 
01_title.pdfAttached File93.38 kBAdobe PDFView/Open
02_certificate.pdf66.29 kBAdobe PDFView/Open
03_declaration.pdf47.68 kBAdobe PDFView/Open
04_acknowledgements.pdf71.93 kBAdobe PDFView/Open
05_abstract.pdf84.62 kBAdobe PDFView/Open
06_contents.pdf101.46 kBAdobe PDFView/Open
07_list of figures.pdf78.7 kBAdobe PDFView/Open
08_glossary.pdf158.35 kBAdobe PDFView/Open
09_chapter 1.pdf239.47 kBAdobe PDFView/Open
10_chapter 2.pdf178.38 kBAdobe PDFView/Open
11_chapter 3.pdf274.82 kBAdobe PDFView/Open
12_chapter 4.pdf203.14 kBAdobe PDFView/Open
13_chapter 5.pdf235.13 kBAdobe PDFView/Open
14_chapter 6.pdf251.81 kBAdobe PDFView/Open
15_chapter 7.pdf196.33 kBAdobe PDFView/Open
16_chapter 8.pdf135.79 kBAdobe PDFView/Open
17_bibliography.pdf114.73 kBAdobe PDFView/Open


Items in Shodhganga are protected by copyright, with all rights reserved, unless otherwise indicated.