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

Jao, Fang-Kai

Permalink

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

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

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