Counterexamples to a Conjecture of Harris on Hall Ratio

DOI10.1137/18M1229420zbMATH Open1493.05095arXiv1811.11116OpenAlexW2903461617WikidataQ113779098 ScholiaQ113779098MaRDI QIDQ5093587FDOQ5093587

Authors: Adam Blumenthal, Bernard Lidický, Ryan R. Martin, Florian Pfender, Jan Volec, Serguei Norine 

Publication date: 28 July 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: The Hall ratio of a graph $G$ is the maximum value of $v(H)/alpha(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.

Full work available at URL: https://arxiv.org/abs/1811.11116

Recommendations

• A counterexample to a conjecture of Hasson
• scientific article; zbMATH DE number 5938984
• Minimal counterexamples to a conjecture of Hall and Paige
• On Hall's conjecture
• A counterexample to a conjecture of Hutchinson and Lai
• On a conjecture of Harris
• On a counter-example to the Hirsch conjecture
• Counterexample to a conjecture of H. Hopf
• A counter-example to Hausmann's conjecture
• Counterexamples to Hedetniemi's conjecture

zbMATH Keywords

random graphsindependent setsHall ratiofractional colorings

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Fractional graph theory, fuzzy graph theory (05C72)

Cites Work

• Title not available (Why is that?)
• Relations among the fractional chromatic, choice, Hall, and Hall-condition numbers of simple graphs
• Title not available (Why is that?)
• A note on Ramsey numbers
• On the independence number of random graphs
• The chromatic number of random graphs
• The list chromatic number of graphs with small clique number
• Limit theorems for complete subgraphs of random graphs
• The fractional chromatic number, the Hall ratio, and the lexicographic product
• Dense induced bipartite subgraphs in triangle-free graphs
• Some results on chromatic number as a function of triangle count
• Separation choosability and dense bipartite induced subgraphs
• 1-subdivisions, the fractional chromatic number and the Hall ratio

Cited In (6)

• Flexible list colorings: maximizing the number of requests satisfied
• Some results on chromatic number as a function of triangle count
• 1-subdivisions, the fractional chromatic number and the Hall ratio
• A function related to the Hall ratio
• Search for good examples of Hall’s conjecture
• A counterexample to a conjecture concerning the Hall-Wellner band

This page was built for publication: Counterexamples to a Conjecture of Harris on Hall Ratio

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5093587)