Extremal problems for labelling of graphs and distance in digraphs

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].

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2013

Author dc:creator

• Jahanbekam, Sogol

Contributors dc:contributor

• Furedi, Zoltan
• West, Douglas B.
• Kostochka, Alexandr V.
• Zhu, Xuding

• Graph Coloring
• Graph Labelling
• Ramsey Numbers
• AntiRamsey Graph Theory
• Weak Diameter in Digraphs
• Matching in Graphs

Statement dc:rights

• Copyright 2013 by Sogol Jahanbekam. All rights reserved.

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/45527

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/45527