University of Illinois Urbana-Champaign

On vertex degrees, graph decomposition, and circular chromatic Ramsey number

Jao, Fang-Kai

Content Files
Fang-Kai_Jao.pdf

Permalink

https://hdl.handle.net/2142/44320

Description

Title
On vertex degrees, graph decomposition, and circular chromatic Ramsey number
Author(s)
Jao, Fang-Kai
Issue Date
2013-05-24T22:07:39Z
Director of Research (if dissertation) or Advisor (if thesis)
West, Douglas B.
Doctoral Committee Chair(s)
Kostochka, Alexandr V.
Committee Member(s)
  • West, Douglas B.
  • Balogh, József
Department of Study
Mathematics
Discipline
Mathematics
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Date of Ingest
2013-05-24T22:07:39Z
Keyword(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}.
Graduation Semester
2013-05
Permalink
http://hdl.handle.net/2142/44320
Copyright and License Information
Copyright 2013 Fang-Kai Jao

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Mathematics