University of Illinois Urbana-Champaign

Extremal problems on edge-colorings, independent sets, and cycle spectra of graphs

Milans, Kevin G.

Content Files
Milans_Kevin.pdf

Permalink

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

Description

Title
Extremal problems on edge-colorings, independent sets, and cycle spectra of graphs
Author(s)
Milans, Kevin G.
Issue Date
2010-08-20T17:57:12Z
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.
  • Jockusch, Carl G., Jr.
  • Vijay, Sujith
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
2010-08-20T17:57:12Z
Keyword(s)
  • Graph Theory
  • Extremal Problems
  • Ramsey Theory
Abstract
We study problems in extremal graph theory with respect to edge-colorings, independent sets, and cycle spectra. In Chapters 2 and 3, we present results in Ramsey theory, where we seek Ramsey host graphs with small maximum degree. In Chapter 4, we study a Ramsey-type problem on edge-labeled trees, where we seek subtrees that have a small number of path-labels. In Chapter 5, we examine parity edge-colorings, which have connections to additive combinatorics and the minimum dimension of a hypercube in which a tree embeds. In Chapter 6, we prove results on the chromatic number of circle graphs with clique number at most 3. The tournament analogue of an independent set is an acyclic set. In Chapter 7, we present results on the size of maximum acyclic sets in k-majority tournaments. In Chapter 8, we prove a lower bound on the size of the cycle spectra of Hamiltonian graphs.
Graduation Semester
2010-08
Permalink
http://hdl.handle.net/2142/16762
Copyright and License Information
Copyright 2010 Kevin G. Milans

Owning Collections

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