Files in this item
Files  Description  Format 

application/pdf Ilkyoo_Choi.pdf (623kB)  (no description provided) 
Description
Title:  Extremal problems on variations of graph colorings 
Author(s):  Choi, Ilkyoo 
Director of Research:  Kostochka, Alexandr V. 
Doctoral Committee Chair(s):  Reznick, Bruce 
Doctoral Committee Member(s):  Kostochka, Alexandr V.; West, Douglas B.; Lidicky, Bernard 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Graph Theory
Graph Coloring Choosability List Chromatic Number Discharging 
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 BorodinKostochka 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 BorodinKostochka 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 6cycles is 5choosable, and they conjectured that the only case when it is not 4choosable is when the graph contains $K_5$. We disprove this conjecture by constructing a family of graphs containing neither 6cycles nor $K_5$ that are not even 4colorable. 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 6cycles nor $K^_5$ are 4choosable. 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. 
Issue Date:  20140530 
URI:  http://hdl.handle.net/2142/49578 
Rights Information:  Copyright 2014 Ilkyoo Choi 
Date Available in IDEALS:  20140530 
Date Deposited:  201405 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois