{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/16762"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/16762","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Extremal problems on edge-colorings, independent sets, and cycle spectra of graphs","abstract":"We study problems in extremal graph theory with respect to edge-colorings, independent sets, and cycle spectra. In Chapters 2 and 3, we present results in Ramsey theory, where we seek Ramsey host graphs with small maximum degree. In Chapter 4, we study a Ramsey-type problem on edge-labeled trees, where we seek subtrees that have a small number of path-labels. In Chapter 5, we examine parity edge-colorings, which have connections to additive combinatorics and the minimum dimension of a hypercube in which a tree embeds. In Chapter 6, we prove results on the chromatic number of circle graphs with clique number at most 3. The tournament analogue of an independent set is an acyclic set. In Chapter 7, we present results on the size of maximum acyclic sets in k-majority tournaments. In Chapter 8, we prove a lower bound on the size of the cycle spectra of Hamiltonian graphs.","abstract_html":"We study problems in extremal graph theory with respect to edge-colorings, independent sets, and cycle spectra. In Chapters 2 and 3, we present results in Ramsey theory, where we seek Ramsey host graphs with small maximum degree. In Chapter 4, we study a Ramsey-type problem on edge-labeled trees, where we seek subtrees that have a small number of path-labels. In Chapter 5, we examine parity edge-colorings, which have connections to additive combinatorics and the minimum dimension of a hypercube in which a tree embeds. In Chapter 6, we prove results on the chromatic number of circle graphs with clique number at most 3. The tournament analogue of an independent set is an acyclic set. In Chapter 7, we present results on the size of maximum acyclic sets in k-majority tournaments. In Chapter 8, we prove a lower bound on the size of the cycle spectra of Hamiltonian graphs.","abstract_has_math":false,"creators":["Milans, Kevin G."],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["West, Douglas B.","Kostochka, Alexandr V.","Jockusch, Carl G., Jr.","Vijay, Sujith"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010-08-20T17:57:12Z","date_published":"2010-08-20T17:57:12Z","updated_at":"2026-07-22T22:25:09Z","subjects":["Graph Theory","Extremal Problems","Ramsey Theory"],"languages":["en"],"rights":["Copyright 2010 Kevin G. Milans"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/16762","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["West, Douglas B.","Kostochka, Alexandr V.","Jockusch, Carl G., Jr.","Vijay, Sujith"]},{"key":"dc:creator","label":"Author","values":["Milans, Kevin G."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2010-08-20T17:57:12Z","2010-08"]},{"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 Theory","Extremal Problems","Ramsey Theory"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2010 Kevin G. Milans"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/16762"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We study problems in extremal graph theory with respect to edge-colorings, independent sets, and cycle spectra. In Chapters 2 and 3, we present results in Ramsey theory, where we seek Ramsey host graphs with small maximum degree. In Chapter 4, we study a Ramsey-type problem on edge-labeled trees, where we seek subtrees that have a small number of path-labels. In Chapter 5, we examine parity edge-colorings, which have connections to additive combinatorics and the minimum dimension of a hypercube in which a tree embeds. In Chapter 6, we prove results on the chromatic number of circle graphs with clique number at most 3. The tournament analogue of an independent set is an acyclic set. In Chapter 7, we present results on the size of maximum acyclic sets in k-majority tournaments. In Chapter 8, we prove a lower bound on the size of the cycle spectra of Hamiltonian graphs.","Item withdrawn by Alexis Thompson (athmpsn1@illinois.edu) on 2010-07-15T19:06:20Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Milans_Kevin.pdf: 949867 bytes, checksum: 4c2164e5db50771fcd467e100f4b52a8 (MD5)","Made available in DSpace on 2010-08-20T17:57:12Z (GMT). No. of bitstreams: 2 Milans_Kevin.pdf: 949867 bytes, checksum: 4c2164e5db50771fcd467e100f4b52a8 (MD5) license.txt: 4060 bytes, checksum: a5eb72f176eaad29320a4a460ee71718 (MD5)"]},{"key":"dc:title","label":"Title","values":["Extremal problems on edge-colorings, independent sets, and cycle spectra of graphs"]}]}],"canonical_facts":{"dc:contributor":["West, Douglas B.","Kostochka, Alexandr V.","Jockusch, Carl G., Jr.","Vijay, Sujith"],"dc:creator":["Milans, Kevin G."],"dc:date":["2010-08-20T17:57:12Z","2010-08"],"dc:description":["We study problems in extremal graph theory with respect to edge-colorings, independent sets, and cycle spectra. In Chapters 2 and 3, we present results in Ramsey theory, where we seek Ramsey host graphs with small maximum degree. In Chapter 4, we study a Ramsey-type problem on edge-labeled trees, where we seek subtrees that have a small number of path-labels. In Chapter 5, we examine parity edge-colorings, which have connections to additive combinatorics and the minimum dimension of a hypercube in which a tree embeds. In Chapter 6, we prove results on the chromatic number of circle graphs with clique number at most 3. The tournament analogue of an independent set is an acyclic set. In Chapter 7, we present results on the size of maximum acyclic sets in k-majority tournaments. In Chapter 8, we prove a lower bound on the size of the cycle spectra of Hamiltonian graphs.","Item withdrawn by Alexis Thompson (athmpsn1@illinois.edu) on 2010-07-15T19:06:20Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Milans_Kevin.pdf: 949867 bytes, checksum: 4c2164e5db50771fcd467e100f4b52a8 (MD5)","Made available in DSpace on 2010-08-20T17:57:12Z (GMT). No. of bitstreams: 2 Milans_Kevin.pdf: 949867 bytes, checksum: 4c2164e5db50771fcd467e100f4b52a8 (MD5) license.txt: 4060 bytes, checksum: a5eb72f176eaad29320a4a460ee71718 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/16762"],"dc:language":["en"],"dc:rights":["Copyright 2010 Kevin G. Milans"],"dc:subject":["Graph Theory","Extremal Problems","Ramsey Theory"],"dc:title":["Extremal problems on edge-colorings, independent sets, and cycle spectra of graphs"],"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:09Z"}