Dissertation
Extremal problems for labelling of graphs and distance in digraphs
(2013)
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].
Keywords
- Graph Coloring,
- Graph Labelling,
- Ramsey Numbers,
- AntiRamsey Graph Theory,
- Weak Diameter in Digraphs,
- Matching in Graphs
Disciplines
Publication Date
August 22, 2013
Degree
Ph.D.
Field of study
Mathematics
Department
Mathematics
Advisors
Douglas B. West
Comments
Copyright 2013 by Sogol Jahanbekam. All rights reserved.
This dissertation can also be found on the IDEALS repository at this link.
Citation Information
Sogol Jahanbekam. "Extremal problems for labelling of graphs and distance in digraphs" (2013) Available at: http://works.bepress.com/sogol-jahanbekam/15/