Files in this item



application/pdfSogol_Jahanbekam.pdf (1MB)
(no description provided)PDF


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
Degree Granting Institution:University of Illinois at Urbana-Champaign
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
Rights Information:Copyright 2013 by Sogol Jahanbekam. All rights reserved.
Date Available in IDEALS:2013-08-22
Date Deposited:2013-08

This item appears in the following Collection(s)

Item Statistics