Counterexamples to a conjecture of Harris on Hall ratio

2018/11/27 by Blumenthal, Adam, Lidicky, Bernard, Martin, Ryan R. +3
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1811.11116

Abstract

The Hall ratio of a graph G is the maximum value of v(H) / α(H) taken over all non-null subgraphs H of G. For any graph, the Hall ratio is a lower-bound on its fractional chromatic number. In this note, we present various constructions of graphs whose fractional chromatic number grows much faster than their Hall ratio. This refutes a conjecture of Harris.

Related

• Fractional chromatic number vs. Hall ratio
• 1-subdivisions, fractional chromatic number and Hall ratio
• Counterexamples to Hedetniemi's conjecture
• Chromatic index determined by fractional chromatic index
• Fractional total colourings of graphs of high girth