{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/49578"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/49578","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Extremal problems on variations of graph colorings","abstract":"This thesis investigates various coloring problems in graph theory. Graph coloring is an essential part of combinatorics and discrete mathematics, as it deals with the fundamental problem of partitioning objects so that each part satisfies a certain condition. In particular, we study how forbidding certain structures (subgraphs) affects a given coloring parameter. Open since 1977, the Borodin--Kostochka Conjecture states that given a graph $G$ with maximum degree $\\Delta(G)$ at least 9, if $G$ has no clique of size $\\Delta(G)$, then $G$ is $(\\Delta(G)-1)$-colorable. The current best result by Reed shows that the statement of the Borodin--Kostochka Conjecture is true for graphs with maximum degree at least $10^{14}$. We produce a result of this type for the list chromatic number; namely, we prove that given a graph $G$ with maximum degree at least $10^{20}$, if $G$ has no clique of size $\\Delta(G)$, then $G$ is $(\\Delta(G)-1)$-choosable. Cai, Wang, and Zhu proved that a toroidal graph with no 6-cycles is 5-choosable, and they conjectured that the only case when it is not 4-choosable is when the graph contains $K_5$. We disprove this conjecture by constructing a family of graphs containing neither 6-cycles nor $K_5$ that are not even 4-colorable. This family is embeddable not only on a torus, but also on any surface except the plane and the projective plane. We prove a slightly weaker statement suggested by Zhu that toroidal graphs containing neither 6-cycles nor $K^-_5$ are 4-choosable. We also study questions regarding variants of coloring. We provide additional positive support for a question by \\v Skrekovski regarding choosability with separation for planar graphs, and we completely answer a question by Raspaud and Wang regarding vertex arboricity for toroidal graphs. We also improve results regarding improper coloring of planar graphs, responding to a question of Montassier and Ochem.","abstract_html":"This thesis investigates various coloring problems in graph theory. Graph coloring is an essential part of combinatorics and discrete mathematics, as it deals with the fundamental problem of partitioning objects so that each part satisfies a certain condition. In particular, we study how forbidding certain structures (subgraphs) affects a given coloring parameter. Open since 1977, the Borodin--Kostochka Conjecture states that given a graph $G$ with maximum degree $\\Delta(G)$ at least 9, if $G$ has no clique of size $\\Delta(G)$, then $G$ is $(\\Delta(G)-1)$-colorable. The current best result by Reed shows that the statement of the Borodin--Kostochka Conjecture is true for graphs with maximum degree at least <span class=\"etd-inline-math\">10<sup>14</sup></span>. We produce a result of this type for the list chromatic number; namely, we prove that given a graph $G$ with maximum degree at least <span class=\"etd-inline-math\">10<sup>20</sup></span>, if $G$ has no clique of size $\\Delta(G)$, then $G$ is $(\\Delta(G)-1)$-choosable. Cai, Wang, and Zhu proved that a toroidal graph with no 6-cycles is 5-choosable, and they conjectured that the only case when it is not 4-choosable is when the graph contains <span class=\"etd-inline-math\">K<sub>5</sub></span>. We disprove this conjecture by constructing a family of graphs containing neither 6-cycles nor <span class=\"etd-inline-math\">K<sub>5</sub></span> that are not even 4-colorable. This family is embeddable not only on a torus, but also on any surface except the plane and the projective plane. We prove a slightly weaker statement suggested by Zhu that toroidal graphs containing neither 6-cycles nor <span class=\"etd-inline-math\">K<sup>-</sup><sub>5</sub></span> are 4-choosable. We also study questions regarding variants of coloring. We provide additional positive support for a question by \\v Skrekovski regarding choosability with separation for planar graphs, and we completely answer a question by Raspaud and Wang regarding vertex arboricity for toroidal graphs. We also improve results regarding improper coloring of planar graphs, responding to a question of Montassier and Ochem.","abstract_has_math":true,"creators":["Choi, Ilkyoo"],"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.","Reznick, Bruce","West, Douglas B.","Lidicky, Bernard"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-05-30T16:50:51Z","date_published":"2014-05-30T16:50:51Z","updated_at":"2026-07-22T22:25:38Z","subjects":["Graph Theory","Graph Coloring","Choosability","List Chromatic Number","Discharging"],"languages":["en"],"rights":["Copyright 2014 Ilkyoo Choi"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/49578","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kostochka, Alexandr V.","Reznick, Bruce","West, Douglas B.","Lidicky, Bernard"]},{"key":"dc:creator","label":"Author","values":["Choi, Ilkyoo"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-05-30T16:50:51Z","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":["Graph Theory","Graph Coloring","Choosability","List Chromatic Number","Discharging"]}]},{"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 Ilkyoo Choi"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/49578"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This thesis investigates various coloring problems in graph theory. Graph coloring is an essential part of combinatorics and discrete mathematics, as it deals with the fundamental problem of partitioning objects so that each part satisfies a certain condition. In particular, we study how forbidding certain structures (subgraphs) affects a given coloring parameter. Open since 1977, the Borodin--Kostochka Conjecture states that given a graph $G$ with maximum degree $\\Delta(G)$ at least 9, if $G$ has no clique of size $\\Delta(G)$, then $G$ is $(\\Delta(G)-1)$-colorable. The current best result by Reed shows that the statement of the Borodin--Kostochka Conjecture is true for graphs with maximum degree at least $10^{14}$. We produce a result of this type for the list chromatic number; namely, we prove that given a graph $G$ with maximum degree at least $10^{20}$, if $G$ has no clique of size $\\Delta(G)$, then $G$ is $(\\Delta(G)-1)$-choosable. Cai, Wang, and Zhu proved that a toroidal graph with no 6-cycles is 5-choosable, and they conjectured that the only case when it is not 4-choosable is when the graph contains $K_5$. We disprove this conjecture by constructing a family of graphs containing neither 6-cycles nor $K_5$ that are not even 4-colorable. This family is embeddable not only on a torus, but also on any surface except the plane and the projective plane. We prove a slightly weaker statement suggested by Zhu that toroidal graphs containing neither 6-cycles nor $K^-_5$ are 4-choosable. We also study questions regarding variants of coloring. We provide additional positive support for a question by \\v Skrekovski regarding choosability with separation for planar graphs, and we completely answer a question by Raspaud and Wang regarding vertex arboricity for toroidal graphs. We also improve results regarding improper coloring of planar graphs, responding to a question of Montassier and Ochem.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2014-04-23T18:33:09Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Choi_Ilkyoo.pdf: 622640 bytes, checksum: c305a0c9610c6bd0a0c1dfb5a2bfd628 (MD5)","Made available in DSpace on 2014-05-30T16:50:51Z (GMT). No. of bitstreams: 2 Ilkyoo_Choi.pdf: 622640 bytes, checksum: c305a0c9610c6bd0a0c1dfb5a2bfd628 (MD5) license.txt: 4059 bytes, checksum: 2a8f81fd425b27b5fb2495dab9456493 (MD5)"]},{"key":"dc:title","label":"Title","values":["Extremal problems on variations of graph colorings"]}]}],"canonical_facts":{"dc:contributor":["Kostochka, Alexandr V.","Reznick, Bruce","West, Douglas B.","Lidicky, Bernard"],"dc:creator":["Choi, Ilkyoo"],"dc:date":["2014-05-30T16:50:51Z","2014-05"],"dc:description":["This thesis investigates various coloring problems in graph theory. Graph coloring is an essential part of combinatorics and discrete mathematics, as it deals with the fundamental problem of partitioning objects so that each part satisfies a certain condition. In particular, we study how forbidding certain structures (subgraphs) affects a given coloring parameter. Open since 1977, the Borodin--Kostochka Conjecture states that given a graph $G$ with maximum degree $\\Delta(G)$ at least 9, if $G$ has no clique of size $\\Delta(G)$, then $G$ is $(\\Delta(G)-1)$-colorable. The current best result by Reed shows that the statement of the Borodin--Kostochka Conjecture is true for graphs with maximum degree at least $10^{14}$. We produce a result of this type for the list chromatic number; namely, we prove that given a graph $G$ with maximum degree at least $10^{20}$, if $G$ has no clique of size $\\Delta(G)$, then $G$ is $(\\Delta(G)-1)$-choosable. Cai, Wang, and Zhu proved that a toroidal graph with no 6-cycles is 5-choosable, and they conjectured that the only case when it is not 4-choosable is when the graph contains $K_5$. We disprove this conjecture by constructing a family of graphs containing neither 6-cycles nor $K_5$ that are not even 4-colorable. This family is embeddable not only on a torus, but also on any surface except the plane and the projective plane. We prove a slightly weaker statement suggested by Zhu that toroidal graphs containing neither 6-cycles nor $K^-_5$ are 4-choosable. We also study questions regarding variants of coloring. We provide additional positive support for a question by \\v Skrekovski regarding choosability with separation for planar graphs, and we completely answer a question by Raspaud and Wang regarding vertex arboricity for toroidal graphs. We also improve results regarding improper coloring of planar graphs, responding to a question of Montassier and Ochem.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2014-04-23T18:33:09Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Choi_Ilkyoo.pdf: 622640 bytes, checksum: c305a0c9610c6bd0a0c1dfb5a2bfd628 (MD5)","Made available in DSpace on 2014-05-30T16:50:51Z (GMT). No. of bitstreams: 2 Ilkyoo_Choi.pdf: 622640 bytes, checksum: c305a0c9610c6bd0a0c1dfb5a2bfd628 (MD5) license.txt: 4059 bytes, checksum: 2a8f81fd425b27b5fb2495dab9456493 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/49578"],"dc:language":["en"],"dc:rights":["Copyright 2014 Ilkyoo Choi"],"dc:subject":["Graph Theory","Graph Coloring","Choosability","List Chromatic Number","Discharging"],"dc:title":["Extremal problems on variations of graph colorings"],"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"}