2026-09-19T21:08:41Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/45527 2023-07-11 col_2142_5131 col_2142_16340 com_2142_5130 com_2142_16339 com_2142_8903

Furedi, Zoltan West, Douglas B. Kostochka, Alexandr V. West, Douglas B. Zhu, Xuding Jahanbekam, Sogol 2013-08-22T16:46:39Z 2013-08-22T16:46:39Z 2015-08-22T10:00:58Z 2013-08 2013-08-22T16:46:39Z 2013-08 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]. Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-07-03T19:29:17Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 Sogol_thesis.tex: 463350 bytes, checksum: 740087efd3e2345147a762444f8a8499 (MD5) Jahanbeham_Sogol.pdf: 1138212 bytes, checksum: ad92e88369402de4da6eaf573e1a2b6b (MD5) Made available in DSpace on 2013-08-22T16:46:39Z (GMT). No. of bitstreams: 3 Sogol_Jahanbekam.pdf: 1138141 bytes, checksum: a69e3cba558192a8ab8a5fb5735de1f6 (MD5) Sogol_thesis.tex: 463350 bytes, checksum: 740087efd3e2345147a762444f8a8499 (MD5) license.txt: 4066 bytes, checksum: e206322837dc9e2497881f1a23a775d4 (MD5) Restriction data tranferred 2014-07-01T11:20:29-05:00 Original Data Group with Access UIUC Users [automated] Release Date: 2015-08-22 11:49:27 UTC Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Seth Robbins (srobbins@illinois.edu) on 2013-08-22T16:49:28Z Item is restricted until 2015-08-22T16:49:27Z U of I Only Restriction Lifted for Item 45509 on 2015-08-22T10:00:58Z. http://hdl.handle.net/2142/45527 en Copyright 2013 by Sogol Jahanbekam. All rights reserved. Graph Coloring Graph Labelling Ramsey Numbers AntiRamsey Graph Theory Weak Diameter in Digraphs Matching in Graphs Extremal problems for labelling of graphs and distance in digraphs text Mathematics 1257 Mathematics 0439 University of Illinois at Urbana-Champaign Dissertation Ph.D. PHD:Mathematics -UIUC 10KS0439PHD