Htam::SURF

The Summer Undergraduate Research Fellowship (SURF) program allows students to research under the guidance of professors.

I worked with professor Richard M. Wilson the summer of 2006 and 2007.

Summer 2007: On Coloring Claw-Free Graphs

Abstract

A graph G is k-claw-free if no vertex has k pairwise nonadjacent neighbors. A proper k-coloring of G is a map from the vertex set to a set of k colors such that no two adjacent vertices map to the same color. The chromatic number χ(G) is the minimal k such that a proper k-coloring of G exists. The clique number ω(G) is the maximum size of a set of vertices in G that are all pairwise adjacent. The independence number α(G) is the maximum size of a set of vertices in G that are all pairwise non-adjacent.

A theorem of Erdős implies that we can make χ(G) arbitrarily large while fixing ω(G) = 2. Therefore in general we cannot bound χ(G) above by a function of ω(G). In 2005, Chudnovsky and Seymour showed that if G is 3-claw-free with α(G) > 3, then χ(G) < 2ω(G). We attempt to improve upon this result for subclasses of 3-claw-free graphs and also generalize this result to k-claw-free graphs.

A 4-hole is four vertices joined together in a square, but neither of the diagonals is joined. We show that if G is k-claw-free, and 4-hole-free, with α(G) > k, then χ(G) < k (k – 1) ω(G) / 2 – 1.

Paper

Jed Yang, On coloring claw-free graphs, final report, 29 Oct 2007.

Summer 2006: Vertex-Pancyclicity of Hypertournaments

Abstract

A hypertournament, or a k-tournament, on n vertices, 2 < k < n, is a pair T = (V, E), where the vertex set V is a set of size n and the edge set E is the collection of all possible subsets of size k of V, called the edges, each taken in one of its k! possible permutations. A k-tournament is vertex-pancyclic if each vertex is contained in (directed) cycles of all possible lengths. A k-tournament is strong if there is a path from u to v for each pair of distinct vertices u and v. We examine the question posed by Gutin and Yeo about the characterization of vertex-pancyclic hypertournaments. We utilize the majority digraph to reduce a k-tournament to an ordinary tournament (2-tournament). We employ this method to extend Moon's theorem (a tournament is vertex-pancyclic if and only if it is strong) to hypertournaments. We prove that for a k-tournament on n vertices, if k > 8 and n > k + 3, then it is vertex-pancyclic if and only if it is strong. The same conclusion holds if k > 5 and n > k + 4, or if k = 4 and n > 11, or if k = 3 and n > 15. We also find bounds for the generalized problem when we extend vertex-pancyclicity to require d edge-disjoint cycles of each possible length and extend strong connectivity to require d edge-disjoint paths between each pair of vertices. Our results include and extend that of Petrovic and Thomassen.

Paper

Jed Yang, Vertex-pancyclicity of hypertournaments, manuscript, 27 June 2007.

Valid HTML 4.01