Files in this item

FilesDescriptionFormat

application/pdf

Sogol_Jahanbekam.pdf (1MB)
(no description provided)PDF

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 Urbana-Champaign 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,3-Conjecture [41] and the 1,2-Conjecture [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 n-vertex 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 edge-coloring of a complete graph Kn that does not have t edge-disjoint rainbow spanning trees of Kn. For integers t and n, we also determine the maximum number of colors in an edge-coloring 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: 2013-08-22 URI: http://hdl.handle.net/2142/45527 Rights Information: Copyright 2013 by Sogol Jahanbekam. All rights reserved. Date Available in IDEALS: 2013-08-222015-08-22 Date Deposited: 2013-08
﻿