2026-09-19T12:42:34Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/44320 2023-07-11 col_2142_5131 col_2142_16340 com_2142_5130 com_2142_16339 com_2142_8903

West, Douglas B. Kostochka, Alexandr V. West, Douglas B. Balogh, József Jao, Fang-Kai 2013-05-24T22:07:39Z 2013-05-24T22:07:39Z 2013-05 2013-05-24T22:07:39Z 2013-05 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}. Item withdrawn by Alexis Thompson (athmpsn1@illinois.edu) on 2013-04-17T17:53:53Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 kylejao-thesis.tex: 234530 bytes, checksum: 5851acdcf6485f30dc720e230f2d6e47 (MD5) Jao_Fang-Kai.pdf: 478878 bytes, checksum: abe5fe7ec503147414132b9b6c673b24 (MD5) Made available in DSpace on 2013-05-24T22:07:39Z (GMT). No. of bitstreams: 3 Fang-Kai_Jao.pdf: 478878 bytes, checksum: abe5fe7ec503147414132b9b6c673b24 (MD5) kylejao-thesis.tex: 234530 bytes, checksum: 5851acdcf6485f30dc720e230f2d6e47 (MD5) license.txt: 4059 bytes, checksum: 55ad8804d7aa6d85a028c52d41c8e588 (MD5) http://hdl.handle.net/2142/44320 en Copyright 2013 Fang-Kai Jao Vertex degree graph realization graph decomposition tree decomposition Graham--Haggkvist conjecture circular chromatic Ramsey number chromatic Ramsey number parameter Ramsey number On vertex degrees, graph decomposition, and circular chromatic Ramsey number text Mathematics 1257 Mathematics 0439 University of Illinois at Urbana-Champaign Dissertation Ph.D. PHD:Mathematics -UIUC 10KS0439PHD