Files in this item
Files  Description  Format 

application/pdf Sogol_Jahanbekam.pdf (1MB)  (no description provided) 
Description
Title:  Extremal problems for labelling of graphs and distance in digraphs 
Author(s):  Jahanbekam, Sogol 
Director of Research:  West, Douglas B. 
Doctoral Committee Chair(s):  Kostochka, Alexandr V. 
Doctoral Committee Member(s):  West, Douglas B.; Furedi, Zoltan; Zhu, Xuding 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Graph Coloring
Graph Labelling Ramsey Numbers AntiRamsey Graph Theory Weak Diameter in Digraphs Matching in Graphs 
Abstract:  We study several extremal problems in graph labelling and in weak diameter of digraphs. In Chapter 2 we apply the Discharging Method to prove the 1,2,3Conjecture [41] and the 1,2Conjecture [48] for graphs with maximum average degree less than 8/3. Stronger results on these conjectures have been proved, but this is the first application of discharging to them, and the structure theorems and reducibility results are of independent interest. Chapter 2 is based on joint work with D. Cranston and D. West that appears in [17]. In Chapter 3 we focus on digraphs. The weak distance between two vertices x and y in a digraph G is the length of the shortest directed path from x to y or from y to x. We define the weak diameter of a digraph to be the maximum directed distance among all pairs of vertices of the digraph. For a fixed integer D, we determine the minimum number of edges in a digraph with weak diameter at least D, when D = 2, or when the number of vertices of the digraph is very large or small with respect to D. Chapter 3 is based on joint work with Z. Furedi that appears in [26]. In Chapter 4 using Ramsey graphs, we determine the minimum clique size an nvertex graph with chromatic number \chi can have if \chi \geq (n+3)/2. For integers n and t, we determine the maximum number of colors in an edgecoloring of a complete graph Kn that does not have t edgedisjoint rainbow spanning trees of Kn. For integers t and n, we also determine the maximum number of colors in an edgecoloring of Kn that does not have any rainbow spanning subgraph with diameter t. Chapter 4 is based on three papers, the first is joint work with C. Biro and Z. Furedi [11] and the other two are joint work with D. West [36, 37]. 
Issue Date:  20130822 
URI:  http://hdl.handle.net/2142/45527 
Rights Information:  Copyright 2013 by Sogol Jahanbekam. All rights reserved. 
Date Available in IDEALS:  20130822 20150822 
Date Deposited:  201308 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois