Counterexamples to a Conjecture of Harris on Hall Ratio

DOI10.1137/18M1229420MaRDI QIDQ5093587zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

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

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)