{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/78444"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/78444","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Extremal problems in disjoint cycles and graph saturation","abstract":"In this thesis, we tackle two main themes: sufficient conditions for the existence of particular subgraphs in a graph, and variations on graph saturation. Determining whether a graph contains a certain subgraph is a computationally difficult problem; as such, sufficient conditions for the existence of a given subgraph are prized. In Chapter 2, we offer a significant refinement of the Corradi-Hajnal Theorem, which gives sufficient conditions for the existence of a given number of disjoint cycles in a graph. Further, our refined theorem leads to an answer for a question posed by G. Dirac in 1963 regarding the existence of disjoint cycles in graphs with a certain connectivity. This answer comprises Chapter 3. In Chapter 4 we prove a result about equitable coloring: that is, a proper coloring whose color classes all have the same size. Our equitable-coloring result confirms a partial case of a generalized version of the much-studied Chen-Lih-Wu conjecture on equitable coloring. In addition, the equitable-coloring result is equivalent to a statement about the existence of disjoint cycles, contributing to our refinement of the Corradi-Hajnal Theorem. In Chapters 5 and 6, we move to the topic of graph saturation, which is related to the Turan problem. One imagines a set of n vertices, to which edges are added one-by-one so that a forbidden subgraph never appears. At some point, no more edges can be added. The Turan problem asks the maximum number of edges in such a graph; the saturation number, on the other hand, asks the minimum number of edges. Two variations of this parameter are studied. In Chapter 5, we study the saturation of Ramsey-minimal families. Ramsey theory deals with partitioning the edges of graphs so that each partition avoids the particular forbidden subgraph assigned to it. Our motivation for studying these families is that they provide a convincing edge-colored (Ramsey) version of graph saturation. We develop a method, called iterated recoloring, for using results from graph saturation to understand this Ramsey version of saturation. As a proof of concept, we use iterated recoloring to determine the saturation number of the Ramsey-minimal families of matchings and describe the assiociated extremal graphs. An induced version of graph saturation was suggested by Martin and Smith. In order to offer a parameter that is defined for all forbidden graphs, Martin and Smith consider generalized graphs, called trigraphs. Of particular interest is the case when the induced-saturated trigraphs in question are equivalent to graphs. In Chapter 6, we show that a surprisingly large number of families fall into this case. Further, we define and investigate another parameter that is a version of induced saturation that is closer in spirit to the original version of graph saturation, but that is not defined for all forbidden subgraphs.","abstract_html":"In this thesis, we tackle two main themes: sufficient conditions for the existence of particular subgraphs in a graph, and variations on graph saturation. Determining whether a graph contains a certain subgraph is a computationally difficult problem; as such, sufficient conditions for the existence of a given subgraph are prized. In Chapter 2, we offer a significant refinement of the Corradi-Hajnal Theorem, which gives sufficient conditions for the existence of a given number of disjoint cycles in a graph. Further, our refined theorem leads to an answer for a question posed by G. Dirac in 1963 regarding the existence of disjoint cycles in graphs with a certain connectivity. This answer comprises Chapter 3. In Chapter 4 we prove a result about equitable coloring: that is, a proper coloring whose color classes all have the same size. Our equitable-coloring result confirms a partial case of a generalized version of the much-studied Chen-Lih-Wu conjecture on equitable coloring. In addition, the equitable-coloring result is equivalent to a statement about the existence of disjoint cycles, contributing to our refinement of the Corradi-Hajnal Theorem. In Chapters 5 and 6, we move to the topic of graph saturation, which is related to the Turan problem. One imagines a set of n vertices, to which edges are added one-by-one so that a forbidden subgraph never appears. At some point, no more edges can be added. The Turan problem asks the maximum number of edges in such a graph; the saturation number, on the other hand, asks the minimum number of edges. Two variations of this parameter are studied. In Chapter 5, we study the saturation of Ramsey-minimal families. Ramsey theory deals with partitioning the edges of graphs so that each partition avoids the particular forbidden subgraph assigned to it. Our motivation for studying these families is that they provide a convincing edge-colored (Ramsey) version of graph saturation. We develop a method, called iterated recoloring, for using results from graph saturation to understand this Ramsey version of saturation. As a proof of concept, we use iterated recoloring to determine the saturation number of the Ramsey-minimal families of matchings and describe the assiociated extremal graphs. An induced version of graph saturation was suggested by Martin and Smith. In order to offer a parameter that is defined for all forbidden graphs, Martin and Smith consider generalized graphs, called trigraphs. Of particular interest is the case when the induced-saturated trigraphs in question are equivalent to graphs. In Chapter 6, we show that a surprisingly large number of families fall into this case. Further, we define and investigate another parameter that is a version of induced saturation that is closer in spirit to the original version of graph saturation, but that is not defined for all forbidden subgraphs.","abstract_has_math":false,"creators":["Yeager, Elyse Christine"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Kostochka, Alexandr V.","Balogh, Jozsef","Reznick, Bruce A.","Molla, Theodore"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-07-22T22:17:17Z","date_published":"2015-07-22T22:17:17Z","updated_at":"2026-07-22T22:26:11Z","subjects":["equitable coloring","cycles","Corradi-Hajnal","Hajnal-Szemeredi","Chen-Lih-Wu","graph saturation","co-criticality","edge-colored saturation"],"languages":["en"],"rights":["Copyright 2015 by Elyse C. Yeager"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/78444","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kostochka, Alexandr V.","Balogh, Jozsef","Reznick, Bruce A.","Molla, Theodore"]},{"key":"dc:creator","label":"Author","values":["Yeager, Elyse Christine"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-07-22T22:17:17Z","2015-05","2015-04-23","2015-5"]},{"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":["equitable coloring","cycles","Corradi-Hajnal","Hajnal-Szemeredi","Chen-Lih-Wu","graph saturation","co-criticality","edge-colored saturation"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2015 by Elyse C. Yeager"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/78444"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this thesis, we tackle two main themes: sufficient conditions for the existence of particular subgraphs in a graph, and variations on graph saturation. Determining whether a graph contains a certain subgraph is a computationally difficult problem; as such, sufficient conditions for the existence of a given subgraph are prized. In Chapter 2, we offer a significant refinement of the Corradi-Hajnal Theorem, which gives sufficient conditions for the existence of a given number of disjoint cycles in a graph. Further, our refined theorem leads to an answer for a question posed by G. Dirac in 1963 regarding the existence of disjoint cycles in graphs with a certain connectivity. This answer comprises Chapter 3. In Chapter 4 we prove a result about equitable coloring: that is, a proper coloring whose color classes all have the same size. Our equitable-coloring result confirms a partial case of a generalized version of the much-studied Chen-Lih-Wu conjecture on equitable coloring. In addition, the equitable-coloring result is equivalent to a statement about the existence of disjoint cycles, contributing to our refinement of the Corradi-Hajnal Theorem. In Chapters 5 and 6, we move to the topic of graph saturation, which is related to the Turan problem. One imagines a set of n vertices, to which edges are added one-by-one so that a forbidden subgraph never appears. At some point, no more edges can be added. The Turan problem asks the maximum number of edges in such a graph; the saturation number, on the other hand, asks the minimum number of edges. Two variations of this parameter are studied. In Chapter 5, we study the saturation of Ramsey-minimal families. Ramsey theory deals with partitioning the edges of graphs so that each partition avoids the particular forbidden subgraph assigned to it. Our motivation for studying these families is that they provide a convincing edge-colored (Ramsey) version of graph saturation. We develop a method, called iterated recoloring, for using results from graph saturation to understand this Ramsey version of saturation. As a proof of concept, we use iterated recoloring to determine the saturation number of the Ramsey-minimal families of matchings and describe the assiociated extremal graphs. An induced version of graph saturation was suggested by Martin and Smith. In order to offer a parameter that is defined for all forbidden graphs, Martin and Smith consider generalized graphs, called trigraphs. Of particular interest is the case when the induced-saturated trigraphs in question are equivalent to graphs. In Chapter 6, we show that a surprisingly large number of families fall into this case. Further, we define and investigate another parameter that is a version of induced saturation that is closer in spirit to the original version of graph saturation, but that is not defined for all forbidden subgraphs.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2015-07-22 without embargo terms","The student, Elyse Yeager, accepted the attached license on 2015-04-21 at 13:55.","The student, Elyse Yeager, submitted this Dissertation for approval on 2015-04-21 at 14:06.","This Dissertation was approved for publication on 2015-04-23 at 16:21.","DSpace SAF Submission Ingestion Package generated from Vireo submission #7992 on 2015-07-22 at 10:33:07","Made available in DSpace on 2015-07-22T22:17:17Z (GMT). No. of bitstreams: 2 YEAGER-DISSERTATION-2015.pdf: 1085874 bytes, checksum: 453d398d51bd1bad934dd487ebe24241 (MD5) LICENSE.txt: 4209 bytes, checksum: 48e8a30882a00cfd7ff7277b57a5ee62 (MD5) Previous issue date: 2015-04-23"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Extremal problems in disjoint cycles and graph saturation"]}]}],"canonical_facts":{"dc:contributor":["Kostochka, Alexandr V.","Balogh, Jozsef","Reznick, Bruce A.","Molla, Theodore"],"dc:creator":["Yeager, Elyse Christine"],"dc:date":["2015-07-22T22:17:17Z","2015-05","2015-04-23","2015-5"],"dc:description":["In this thesis, we tackle two main themes: sufficient conditions for the existence of particular subgraphs in a graph, and variations on graph saturation. Determining whether a graph contains a certain subgraph is a computationally difficult problem; as such, sufficient conditions for the existence of a given subgraph are prized. In Chapter 2, we offer a significant refinement of the Corradi-Hajnal Theorem, which gives sufficient conditions for the existence of a given number of disjoint cycles in a graph. Further, our refined theorem leads to an answer for a question posed by G. Dirac in 1963 regarding the existence of disjoint cycles in graphs with a certain connectivity. This answer comprises Chapter 3. In Chapter 4 we prove a result about equitable coloring: that is, a proper coloring whose color classes all have the same size. Our equitable-coloring result confirms a partial case of a generalized version of the much-studied Chen-Lih-Wu conjecture on equitable coloring. In addition, the equitable-coloring result is equivalent to a statement about the existence of disjoint cycles, contributing to our refinement of the Corradi-Hajnal Theorem. In Chapters 5 and 6, we move to the topic of graph saturation, which is related to the Turan problem. One imagines a set of n vertices, to which edges are added one-by-one so that a forbidden subgraph never appears. At some point, no more edges can be added. The Turan problem asks the maximum number of edges in such a graph; the saturation number, on the other hand, asks the minimum number of edges. Two variations of this parameter are studied. In Chapter 5, we study the saturation of Ramsey-minimal families. Ramsey theory deals with partitioning the edges of graphs so that each partition avoids the particular forbidden subgraph assigned to it. Our motivation for studying these families is that they provide a convincing edge-colored (Ramsey) version of graph saturation. We develop a method, called iterated recoloring, for using results from graph saturation to understand this Ramsey version of saturation. As a proof of concept, we use iterated recoloring to determine the saturation number of the Ramsey-minimal families of matchings and describe the assiociated extremal graphs. An induced version of graph saturation was suggested by Martin and Smith. In order to offer a parameter that is defined for all forbidden graphs, Martin and Smith consider generalized graphs, called trigraphs. Of particular interest is the case when the induced-saturated trigraphs in question are equivalent to graphs. In Chapter 6, we show that a surprisingly large number of families fall into this case. Further, we define and investigate another parameter that is a version of induced saturation that is closer in spirit to the original version of graph saturation, but that is not defined for all forbidden subgraphs.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2015-07-22 without embargo terms","The student, Elyse Yeager, accepted the attached license on 2015-04-21 at 13:55.","The student, Elyse Yeager, submitted this Dissertation for approval on 2015-04-21 at 14:06.","This Dissertation was approved for publication on 2015-04-23 at 16:21.","DSpace SAF Submission Ingestion Package generated from Vireo submission #7992 on 2015-07-22 at 10:33:07","Made available in DSpace on 2015-07-22T22:17:17Z (GMT). No. of bitstreams: 2 YEAGER-DISSERTATION-2015.pdf: 1085874 bytes, checksum: 453d398d51bd1bad934dd487ebe24241 (MD5) LICENSE.txt: 4209 bytes, checksum: 48e8a30882a00cfd7ff7277b57a5ee62 (MD5) Previous issue date: 2015-04-23"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/78444"],"dc:language":["en"],"dc:rights":["Copyright 2015 by Elyse C. Yeager"],"dc:subject":["equitable coloring","cycles","Corradi-Hajnal","Hajnal-Szemeredi","Chen-Lih-Wu","graph saturation","co-criticality","edge-colored saturation"],"dc:title":["Extremal problems in disjoint cycles and graph saturation"],"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:26:11Z"}