IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

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

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/16762

Files in this item

File Description Format
PDF Milans_Kevin.pdf (950KB) (no description provided) PDF
Title: Extremal problems on edge-colorings, independent sets, and cycle spectra of graphs
Author(s): Milans, Kevin G.
Director of Research: West, Douglas B.
Doctoral Committee Chair(s): Kostochka, Alexandr V.
Doctoral Committee Member(s): West, Douglas B.; Jockusch, Carl G.; Vijay, Sujith
Department / Program: Mathematics
Discipline: Mathematics
Degree Granting Institution: University of Illinois at Urbana-Champaign
Degree: Ph.D.
Genre: Dissertation
Subject(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.
Issue Date: 2010-08-20
URI: http://hdl.handle.net/2142/16762
Rights Information: Copyright 2010 Kevin G. Milans
Date Available in IDEALS: 2010-08-20
Date Deposited: 2010-08
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 307
  • Downloads this Month: 3
  • Downloads Today: 0

Browse

My Account

Information

Access Key