Counterexamples to a Conjecture of Harris on Hall Ratio

DOI10.1137/18M1229420zbMath1493.05095arXiv1811.11116OpenAlexW2903461617WikidataQ113779098 ScholiaQ113779098MaRDI QIDQ5093587

Bernard Lidický, Jan Volec, Adam Blumenthal, Ryan R. Martin, Florian Pfender, 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) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Fractional graph theory, fuzzy graph theory (05C72)

Related Items (1)

Some Results on Chromatic Number as a Function of Triangle Count

Cites Work

• Unnamed Item
• Unnamed Item
• On the independence number of random graphs
• The fractional chromatic number, the Hall ratio, and the lexicographic product
• A note on Ramsey numbers
• Limit theorems for complete subgraphs of random graphs
• The list chromatic number of graphs with small clique number
• Dense induced bipartite subgraphs in triangle-free graphs
• 1-subdivisions, the fractional chromatic number and the Hall ratio
• Some Results on Chromatic Number as a Function of Triangle Count
• Separation Choosability and Dense Bipartite Induced Subgraphs
• The chromatic number of random graphs
• Relations among the fractional chromatic, choice, Hall, and Hall-condition numbers of simple graphs

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