Electronic Theses and Dissertations

# The Fractional Chromatic Number and the Hall Ratio

2016-07-29

## Author

Barnett, Johnathan

PhD Dissertation

## Department

Mathematics and Statistics

Show full item record

## Abstract

All graphs in this paper are both ﬁnite and simple. α(G) is the vertex independence of a graph, G. The Hall ratio of G is deﬁned as ρ(G) = max[n(H) /α(H) |n(H) = |V (H)|and H ⊆ G] where H ⊆ G means that H is a subgraph of G. The chromatic number of G, denoted χ(G), is the smallest number of colors needed to label the vertices of G such that no two adjacent vertices receive the same color. A b-fold coloring of G is an assignment to each vertex of G a set of b colors so that adjacent vertices receive disjoint sets of colors. We then say that G is a:b-colorable if it has a b-fold coloring in which the b colors come from a palette of a colors. The least a for which G has a b-fold coloring from {1,...,a} is the b-fold chromatic number of G and is denoted χb(G). We can now deﬁne the fractional chromatic number of G to be χf(G) = infb χb/ b . It is known that χ(G) ≥ χf(G) ≥ ρ(G) for all G. It is known that, on the class of Kneser graphs, the ratio of the chromatic number to the Hall ratio is unbounded. However, if K is a Kneser graph, then it happens that χf(K) = ρ(K). This begs the question, ”Is χf /ρ bounded on the domain of all ﬁnite simple graphs?” In Chapter 2, we deﬁne a function that should help to identify the Hall ratio of a given graph and we discuss general properties of said function. In Chapter 3, we give results toward answering the question above by considering the lexicographic and disjunctive powers of the graph, W5. In Chapter 4, we give results toward answering the question above by considering the Mycielski graphs.