Files in this item



application/pdfFang-Kai_Jao.pdf (479kB)
(no description provided)PDF


Title:On vertex degrees, graph decomposition, and circular chromatic Ramsey number
Author(s):Jao, Fang-Kai
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
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Vertex degree
graph realization
graph decomposition
tree decomposition
Graham--Haggkvist 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 gap-free if each integer between r and s is present. In Chapter 2, we prove that a gap-free 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ős--Gallai 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 n-4. For k=5 (and n≥4), the answer is ⌊(2n-8)/3⌋ (except one less when n≡1 mod 6). For k≥6 (and n≥k+2), the answer is ⌊(n-6)/(k-4)⌋. 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 T-decomposition 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 T-decompositions for more 2m-regular graphs and m-regular 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_i-regular for all i to have a T-decomposition. One sufficient condition is the existence of a k-edge-coloring 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 edge-coloring 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(k-1) for k∈ℕ-{1}.
Issue Date:2013-05-24
Rights Information:Copyright 2013 Fang-Kai Jao
Date Available in IDEALS:2013-05-24
Date Deposited:2013-05

This item appears in the following Collection(s)

Item Statistics