{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/49480"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/49480","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Extremal problems involving forbidden subgraphs","abstract":"In this thesis, we study extremal problems involving forbidden subgraphs. We are interested in extremal problems over a family of graphs or over a family of hypergraphs. In Chapter 2, we consider improper coloring of graphs without short cycles. We find how sparse an improperly critical graph can be when it has no short cycle. In particular, we find the exact threshold of density of triangle-free $(0,k)$-colorable graphs and we find the asymptotic threshold of density of $(j,k)$-colorable graphs of large girth when $k\\geq 2j+2$. In Chapter 3, we consider other variations of graph coloring. We determine harmonious chromatic number of trees with large maximum degree and show upper bounds of $r$-dynamic chromatic number of graphs in terms of other parameters. In Chapter 4, we consider how dense a hypergraph can be when we forbid some subgraphs. In particular, we characterize hypergraphs with the maximum number of edges that contain no $r$-regular subgraphs. We also establish upper bounds for the number of edges in graphs and hypergraphs with no edge-disjoint equicovering subgraphs.","abstract_html":"In this thesis, we study extremal problems involving forbidden subgraphs. We are interested in extremal problems over a family of graphs or over a family of hypergraphs. In Chapter 2, we consider improper coloring of graphs without short cycles. We find how sparse an improperly critical graph can be when it has no short cycle. In particular, we find the exact threshold of density of triangle-free $(0,k)$-colorable graphs and we find the asymptotic threshold of density of $(j,k)$-colorable graphs of large girth when $k\\geq 2j+2$. In Chapter 3, we consider other variations of graph coloring. We determine harmonious chromatic number of trees with large maximum degree and show upper bounds of $r$-dynamic chromatic number of graphs in terms of other parameters. In Chapter 4, we consider how dense a hypergraph can be when we forbid some subgraphs. In particular, we characterize hypergraphs with the maximum number of edges that contain no $r$-regular subgraphs. We also establish upper bounds for the number of edges in graphs and hypergraphs with no edge-disjoint equicovering subgraphs.","abstract_has_math":true,"creators":["Kim, Jaehoon"],"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.","Weichsel, Paul M.","West, Douglas B.","Lidicky, Bernard"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-05-30T16:46:19Z","date_published":"2014-05-30T16:46:19Z","updated_at":"2026-07-22T22:25:38Z","subjects":["Extremal Graph Theory","Graphs","Graph Coloring","Hypergraphs","Forbidden Subgraphs"],"languages":["en"],"rights":["Copyright 2014 Jaehoon Kim"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/49480","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kostochka, Alexandr V.","Weichsel, Paul M.","West, Douglas B.","Lidicky, Bernard"]},{"key":"dc:creator","label":"Author","values":["Kim, Jaehoon"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-05-30T16:46:19Z","2014-05"]},{"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":["Extremal Graph Theory","Graphs","Graph Coloring","Hypergraphs","Forbidden Subgraphs"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2014 Jaehoon Kim"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/49480"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this thesis, we study extremal problems involving forbidden subgraphs. We are interested in extremal problems over a family of graphs or over a family of hypergraphs. In Chapter 2, we consider improper coloring of graphs without short cycles. We find how sparse an improperly critical graph can be when it has no short cycle. In particular, we find the exact threshold of density of triangle-free $(0,k)$-colorable graphs and we find the asymptotic threshold of density of $(j,k)$-colorable graphs of large girth when $k\\geq 2j+2$. In Chapter 3, we consider other variations of graph coloring. We determine harmonious chromatic number of trees with large maximum degree and show upper bounds of $r$-dynamic chromatic number of graphs in terms of other parameters. In Chapter 4, we consider how dense a hypergraph can be when we forbid some subgraphs. In particular, we characterize hypergraphs with the maximum number of edges that contain no $r$-regular subgraphs. We also establish upper bounds for the number of edges in graphs and hypergraphs with no edge-disjoint equicovering subgraphs.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2014-04-24T20:16:26Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 Kim_Jaehoon.tex: 315562 bytes, checksum: 23600773759e7bf00fd764a619aac66a (MD5) Kim_Jaehoon.pdf: 531955 bytes, checksum: 29882ed9466cf4a4376ebf13047d1141 (MD5)","Made available in DSpace on 2014-05-30T16:46:19Z (GMT). No. of bitstreams: 3 Jaehoon_Kim.pdf: 544575 bytes, checksum: 0f48c4d52c8c0b372b89cc9097036117 (MD5) Kim_Jaehoon.tex: 315562 bytes, checksum: 23600773759e7bf00fd764a619aac66a (MD5) license.txt: 4059 bytes, checksum: 679724f62ef5c0078202c9f5da6fabc5 (MD5)"]},{"key":"dc:title","label":"Title","values":["Extremal problems involving forbidden subgraphs"]}]}],"canonical_facts":{"dc:contributor":["Kostochka, Alexandr V.","Weichsel, Paul M.","West, Douglas B.","Lidicky, Bernard"],"dc:creator":["Kim, Jaehoon"],"dc:date":["2014-05-30T16:46:19Z","2014-05"],"dc:description":["In this thesis, we study extremal problems involving forbidden subgraphs. We are interested in extremal problems over a family of graphs or over a family of hypergraphs. In Chapter 2, we consider improper coloring of graphs without short cycles. We find how sparse an improperly critical graph can be when it has no short cycle. In particular, we find the exact threshold of density of triangle-free $(0,k)$-colorable graphs and we find the asymptotic threshold of density of $(j,k)$-colorable graphs of large girth when $k\\geq 2j+2$. In Chapter 3, we consider other variations of graph coloring. We determine harmonious chromatic number of trees with large maximum degree and show upper bounds of $r$-dynamic chromatic number of graphs in terms of other parameters. In Chapter 4, we consider how dense a hypergraph can be when we forbid some subgraphs. In particular, we characterize hypergraphs with the maximum number of edges that contain no $r$-regular subgraphs. We also establish upper bounds for the number of edges in graphs and hypergraphs with no edge-disjoint equicovering subgraphs.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2014-04-24T20:16:26Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 Kim_Jaehoon.tex: 315562 bytes, checksum: 23600773759e7bf00fd764a619aac66a (MD5) Kim_Jaehoon.pdf: 531955 bytes, checksum: 29882ed9466cf4a4376ebf13047d1141 (MD5)","Made available in DSpace on 2014-05-30T16:46:19Z (GMT). No. of bitstreams: 3 Jaehoon_Kim.pdf: 544575 bytes, checksum: 0f48c4d52c8c0b372b89cc9097036117 (MD5) Kim_Jaehoon.tex: 315562 bytes, checksum: 23600773759e7bf00fd764a619aac66a (MD5) license.txt: 4059 bytes, checksum: 679724f62ef5c0078202c9f5da6fabc5 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/49480"],"dc:language":["en"],"dc:rights":["Copyright 2014 Jaehoon Kim"],"dc:subject":["Extremal Graph Theory","Graphs","Graph Coloring","Hypergraphs","Forbidden Subgraphs"],"dc:title":["Extremal problems involving forbidden subgraphs"],"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:38Z"}