Semester

Summer

Date of Graduation

2009

Document Type

Dissertation

Degree Type

PhD

College

Eberly College of Arts and Sciences

Department

Mathematics

Committee Chair

Cun-Quan Zhang.

Abstract

Part 1. The Fulkerson Conjecture states that every cubic bridgeless graph has six perfect matchings such that every edge of the graph is contained in exactly two of these perfect matchings. In this paper, we verify the conjecture for some families of snarks (Goldberg snarks, flower snarks) by using a technical lemma.;Part 2. A star coloring of an undirected graph G is a proper vertex coloring of G such that any path of length 3 in G is not bi-colored. The star chromatic number of a family of graphs G , denoted by chis( G ), is the minimum number of colors that are necessary to star color any graph belonging to G . Let FD be the family of all graphs with maximum degree at most Delta. It was proved by G. Fertin, A. Raspaud and B. Reed (JGT 2004) that chi s( FD ) ≥ 2Delta where 1 ≤ Delta ≤ 3. In this paper, this result is further generalized for every positive integer Delta. That is, chi s FD ≥ 2Delta for every Delta ∈ Z+ . It was proved by M. Albertson, G. Chappell, H. Kierstead, A. Kundgen, R. Ramamurthi (EJC 2004) that chis( FD ) ≤ Delta(Delta - 1) + 2. In this paper, a simplified proof is given and this result is further improved for non Delta-regular graph to chis FngD ≤ Delta(Delta - 1) + 1 where FngD is the family of non-regular graphs with maximum degree Delta.;Part 3. There are two famous conjectures about integer flows, the 5-flow conjecture raised by Tutte and the orientable 5-cycle double cover by Archdeacon [1] and Jaeger [15]. It is known that the orientable 5-cycle double cover conjecture implies the 5-flow conjecture. But the converse is not known to hold. In this paper, we try to use the reductions of incomplete integer flows to lead us in a direction to attack the problem.

Download

Share

COinS