Counterexamples to a Conjecture of Harris on Hall Ratio
Date
2022-09
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Society for Industrial and Applied Mathematics
Abstract
The Hall ratio of a graph G is the maximum value of v(H)/α(H) taken over all non-null subgraphs H ⊆ 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.
Series Number
Journal Issue
Is Version Of
Versions
Preprint
Counterexamples to a conjecture of Harris on Hall ratio
(
2020-04-24)
The Hall ratio of a graph G is the maximum value of v(H)/α(H) taken over all non-null subgraphs H ⊆ 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.
Series
Academic or Administrative Unit
Type
Article
Comments
This article is published as Blumenthal, Adam, Bernard Lidicky, Ryan R. Martin, Sergey Norin, Florian Pfender, and Jan Volec. "Counterexamples to a conjecture of Harris on Hall ratio." SIAM Journal on Discrete Mathematics 36, no. 3 (2022): 1678-1686. https://doi.org/10.1137/18M1229420. Posted with permission.
Rights Statement
© 2022, Society for Industrial and Applied Mathematics.