The Fractional Chromatic Number and the Hall Ratio

Abstract

All graphs in this paper are both finite and simple. α(G) is the vertex independence of a graph, G. The Hall ratio of G is defined 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 define 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 finite simple graphs?” In Chapter 2, we define 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.