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

Milans, Kevin G.

Permalink

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

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

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