{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/45527"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/45527","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Extremal problems for labelling of graphs and distance in digraphs","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].","abstract_html":"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].","abstract_has_math":false,"creators":["Jahanbekam, Sogol"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Furedi, Zoltan","West, Douglas B.","Kostochka, Alexandr V.","Zhu, Xuding"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-08-22T16:46:39Z","date_published":"2013-08-22T16:46:39Z","updated_at":"2026-07-22T22:25:36Z","subjects":["Graph Coloring","Graph Labelling","Ramsey Numbers","AntiRamsey Graph Theory","Weak Diameter in Digraphs","Matching in Graphs"],"languages":["en"],"rights":["Copyright 2013 by Sogol Jahanbekam. All rights reserved."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/45527","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Furedi, Zoltan","West, Douglas B.","Kostochka, Alexandr V.","Zhu, Xuding"]},{"key":"dc:creator","label":"Author","values":["Jahanbekam, Sogol"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-08-22T16:46:39Z","2015-08-22T10:00:58Z","2013-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graph Coloring","Graph Labelling","Ramsey Numbers","AntiRamsey Graph Theory","Weak Diameter in Digraphs","Matching in Graphs"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 by Sogol Jahanbekam. All rights reserved."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/45527"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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."]},{"key":"dc:title","label":"Title","values":["Extremal problems for labelling of graphs and distance in digraphs"]}]}],"canonical_facts":{"dc:contributor":["Furedi, Zoltan","West, Douglas B.","Kostochka, Alexandr V.","Zhu, Xuding"],"dc:creator":["Jahanbekam, Sogol"],"dc:date":["2013-08-22T16:46:39Z","2015-08-22T10:00:58Z","2013-08"],"dc:description":["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."],"dc:identifier":["http://hdl.handle.net/2142/45527"],"dc:language":["en"],"dc:rights":["Copyright 2013 by Sogol Jahanbekam. All rights reserved."],"dc:subject":["Graph Coloring","Graph Labelling","Ramsey Numbers","AntiRamsey Graph Theory","Weak Diameter in Digraphs","Matching in Graphs"],"dc:title":["Extremal problems for labelling of graphs and distance in digraphs"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:36Z"}