Files in this item
Files  Description  Format 

application/pdf FangKai_Jao.pdf (479kB)  (no description provided) 
Description
Title:  On vertex degrees, graph decomposition, and circular chromatic Ramsey number 
Author(s):  Jao, FangKai 
Director of Research:  West, Douglas B. 
Doctoral Committee Chair(s):  Kostochka, Alexandr V. 
Doctoral Committee Member(s):  West, Douglas B.; Balogh, József 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Vertex degree
graph realization graph decomposition tree decomposition GrahamHaggkvist conjecture circular chromatic Ramsey number chromatic Ramsey number parameter Ramsey number 
Abstract:  In this thesis, we study extremal problems about vertex degrees and a variant of Ramsey number of graphs, and also structural problems about graph decomposition. In a list (d_1,...,d_n) of positive integers, let r and s denote the largest and smallest entries. A list is gapfree if each integer between r and s is present. In Chapter 2, we prove that a gapfree list with even sum is graphic if it has at least r+(r+s+1)/(2s) terms. With no restriction on gaps, length at least (r+s+1)^2/(4s) suffices, as proved by Zverovich and Zverovich. Both bounds are sharp within 1. When the gaps between consecutive terms are bounded by g, we prove a more general length threshold that includes both of these results. As a tool, we prove that if a positive list d with even sum has no repeated entries other than r and s (and the length exceeds r), then to prove that d is graphic it suffices to check only the ℓth ErdősGallai inequality, where ℓ=max{k: d_k≥k} For outerplanar graphs on n vertices, we determine the maximum number of vertices of degree at least k. For k=4 (and n≥7), the answer is n4. For k=5 (and n≥4), the answer is ⌊(2n8)/3⌋ (except one less when n≡1 mod 6). For k≥6 (and n≥k+2), the answer is ⌊(n6)/(k4)⌋. As a tool, we determine the maximum sum of the degrees of s vertices. We also determine the maximum sum of the degrees of the vertices with degree at least k. A Tdecomposition of a graph G is a decomposition of G into isomorphic copies of T. Let T be a tree with m edges. In Chapter 3, we extend the ideas of Snevily and Avgustinovitch to prove the existence of Tdecompositions for more 2mregular graphs and mregular bipartite graphs. In particular, for r_1,...,r_k with ∑_{i=1}^k r_i=m, we seek sufficient conditions for every cartesian product of graphs G_1,...,G_k with G_i being 2r_iregular for all i to have a Tdecomposition. One sufficient condition is the existence of a kedgecoloring of T with r_i edges of color i such that every path in T uses some color once or twice. Another sufficient condition is that r_i≤⌈(m+1)/2⌉ for all i and m/k<4 Finally, in Chapter 4, we introduce the circular chromatic Ramsey number R_{χ_c}(F,G) as the infimum of the circular chromatic numbers χ_c(H) of graphs H such that every red/blue edgecoloring of H yields a red copy of F or a blue copy of G. We prove R_{χ_c}(K_3,K_3)=6 and R_{χ_c}(K_3,K_4)=9. Also, if 2<χ_c(G)≤5/2, then R_{χ_c}(G,G)=4. Furthermore, no graph has circular chromatic Ramsey number between 4 and 5. Also, with R_{χ_c}(z)=inf{R_{χ_c}(G): χ_c(G)≥z}, we prove R_{χ_c}(k)≤k(k1) for k∈ℕ{1}. 
Issue Date:  20130524 
URI:  http://hdl.handle.net/2142/44320 
Rights Information:  Copyright 2013 FangKai Jao 
Date Available in IDEALS:  20130524 
Date Deposited:  201305 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

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