## Files in this item

FilesDescriptionFormat

application/pdf

Fang-Kai_Jao.pdf (479kB)
(no description provided)PDF

## Description

 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 Discipline: Mathematics Degree Granting Institution: University of Illinois at Urbana-Champaign Degree: Ph.D. Genre: Dissertation 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 URI: http://hdl.handle.net/2142/44320 Rights Information: Copyright 2013 Fang-Kai Jao Date Available in IDEALS: 2013-05-24 Date Deposited: 2013-05
﻿