Files in this item
Files  Description  Format 

application/pdf SANTANADISSERTATION2016.pdf (850kB)  (no description provided) 
Description
Title:  Extremal problems on cycle structure and colorings of graphs 
Author(s):  Santana, Michael L 
Director of Research:  Kostochka, Alexandr V 
Doctoral Committee Chair(s):  Reznick, Bruce 
Doctoral Committee Member(s):  West, Douglas B; Molla, Theodore 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  graphs
cycles strong edgecolorings 
Abstract:  In this Thesis, we consider two main themes: conditions that guarantee diverse cycle structure within a graph, and the existence of strong edgecolorings for a specific family of graphs. In Chapter 2 we consider a question closely related to the MatthewsSumner conjecture, which states that every 4connected clawfree graph is Hamiltonian. Since there exists an infinite family of 4connected clawfree graphs that are not pancyclic, Gould posed the problem of characterizing the pairs of graphs, {X,Y}, such that every 4connected {X,Y}free graph is pancyclic. In this chapter we describe a family of pairs of graphs such that if every 4connected {X,Y}free graph is pancyclic, then {X,Y} is in this family. Furthermore, we show that every 4connected {K_(1,3),N(4,1,1)}free graph is pancyclic. This result, together with several others, completes a characterization of the family of subgraphs, F such that for all H in ∈, every 4connected {K_(1,3), H}free graph is pancyclic. In Chapters and 4 we consider refinements of results on cycles and chorded cycles. In 1963, Corrádi and Hajnal proved a conjecture of Erdös, showing that every graph G on at least 3k vertices with minimum degree at least 2k contains k disjoint cycles. This result was extended by Enomoto and Wang, who independently proved that graphs on at least 3kvertices with minimum degreesum at least 4k  1 also contain k disjoint cycles. Both results are best possible, and recently, Kierstead, Kostochka, Molla, and Yeager characterized their sharpness examples. A chorded cycle analogue to the result of Corrádi and Hajnal was proved by Finkel, and a similar analogue to the result of Enomoto and Wang was proved by Chiba, Fujita, Gao, and Li. In Chapter 3 we characterize the sharpness examples to these statements, which provides a chorded cycle analogue to the characterization of Kierstead et al. In Chapter 4 we consider another result of Chiba et al., which states that for all integers r and s with r + s ≥ 1, every graph G on at least 3r + 4s vertices with ẟ(G) ≥ 2r+3s contains r disjoint cycles and s disjoint chorded cycles. We provide a characterization of the sharpness examples to this result, which yields a transition between the characterization of Kierstead et al. and the main result of Chapter 3. In Chapter 5 we move to the topic of edgecolorings, considering a variation known as strong edgecoloring. In 1990, Faudree, Gyárfás, Schelp, and Tuza posed several conjectures regarding strong edgecolorings of subcubic graphs. In particular, they conjectured that every subcubic planar graph has a strong edgecoloring using at most nine colors. We prove a slightly stronger form of this conjecture, showing that it holds for all subcubic planar loopless multigraphs. 
Issue Date:  20160707 
Type:  Thesis 
URI:  http://hdl.handle.net/2142/92769 
Rights Information:  Copyright 2016 Michael Santana 
Date Available in IDEALS:  20161110 
Date Deposited:  201608 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

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