{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T21:38:36Z","timestamp":1757626716330,"version":"3.44.0"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T00:00:00Z","timestamp":1751587200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T00:00:00Z","timestamp":1751587200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Swiss Federal Institute of Technology Zurich"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2025,8]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Given a graph <jats:italic>G<\/jats:italic>, its <jats:italic>Hall ratio<\/jats:italic>\n            <jats:inline-formula>\n              <jats:tex-math>$$\\rho (G)=\\max _{H\\subseteq G}\\frac{|V(H)|}{\\alpha (H)}$$<\/jats:tex-math>\n            <\/jats:inline-formula> forms a natural lower bound for its fractional chromatic number <jats:inline-formula>\n              <jats:tex-math>$$\\chi _f(G)$$<\/jats:tex-math>\n            <\/jats:inline-formula>. A recent line of research studied the question whether <jats:inline-formula>\n              <jats:tex-math>$$\\chi _f(G)$$<\/jats:tex-math>\n            <\/jats:inline-formula> can be bounded in terms of a (linear) function of <jats:inline-formula>\n              <jats:tex-math>$$\\rho (G)$$<\/jats:tex-math>\n            <\/jats:inline-formula>. Dvo\u0159\u00e1k, Ossona de Mendez and Wu\u00a0[6, <jats:italic>Combinatorica<\/jats:italic>, 2020] gave a negative answer by proving the existence of graphs with bounded Hall ratio and arbitrarily large fractional chromatic number. In this paper, we solve two follow-up problems that were raised by Dvo\u0159\u00e1k et al. The first problem concerns determining the growth of <jats:italic>g<\/jats:italic>(<jats:italic>n<\/jats:italic>), defined as the maximum ratio <jats:inline-formula>\n              <jats:tex-math>$$\\frac{\\chi _f(G)}{\\rho (G)}$$<\/jats:tex-math>\n            <\/jats:inline-formula> among all <jats:italic>n<\/jats:italic>-vertex graphs. Dvo\u0159\u00e1k et al. obtained the bounds <jats:inline-formula>\n              <jats:tex-math>$$\\Omega (\\log \\log n) \\le g(n)\\le O(\\log n)$$<\/jats:tex-math>\n            <\/jats:inline-formula>. We show that the true value is close to the upper bound: <jats:inline-formula>\n              <jats:tex-math>$$g(n)=(\\log n)^{1-o(1)}$$<\/jats:tex-math>\n            <\/jats:inline-formula>. The second problem posed by Dvo\u0159\u00e1k et al. asks for the existence of graphs with bounded Hall ratio, arbitrarily large fractional chromatic number and such that every subgraph contains an independent set that touches a constant fraction of its edges. We show that such graphs indeed exist.<\/jats:p>","DOI":"10.1007\/s00493-025-00164-0","type":"journal-article","created":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T05:57:23Z","timestamp":1751608643000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fractional Chromatic Number Vs. Hall Ratio"],"prefix":"10.1007","volume":"45","author":[{"given":"Raphael","family":"Steiner","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,7,4]]},"reference":[{"issue":"3","key":"164_CR1","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0097-3165(78)90023-7","volume":"25","author":"J B\u00e1r\u00e1ny","year":"1978","unstructured":"B\u00e1r\u00e1ny, J.: A short proof of Kneser\u2019s conjecture. J. Comb. Theory Ser. A 25(3), 325\u2013326 (1978)","journal-title":"J. Comb. Theory Ser. A"},{"key":"164_CR2","unstructured":"Barnett, J.B.: The Fractional chromatic number and the Hall ratio. PhD thesis, Auburn University, (2016)"},{"issue":"3","key":"164_CR3","doi-asserted-by":"publisher","first-page":"1678","DOI":"10.1137\/18M1229420","volume":"36","author":"A Blumenthal","year":"2022","unstructured":"Blumenthal, A., Lidick\u00fd, B., Martin, R.R., Norin, S., Pfender, F., Volec, J.: Counterexamples to a conjecture of Harris on Hall ratio. SIAM J. Discret. Math. 36(3), 1678\u20131686 (2022)","journal-title":"SIAM J. Discret. Math."},{"issue":"16","key":"164_CR4","doi-asserted-by":"publisher","first-page":"1988","DOI":"10.1016\/j.disc.2005.09.020","volume":"306","author":"M Cropper","year":"2006","unstructured":"Cropper, M., Gy\u00e1rf\u00e1s, A., Lehel, J.: Hall ratio of the Mycielski graphs. Discret. Math. 306(16), 1988\u20131990 (2006)","journal-title":"Discret. Math."},{"issue":"1\u20133","key":"164_CR5","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0012-365X(01)00117-0","volume":"241","author":"A Daneshgar","year":"2001","unstructured":"Daneshgar, A., Hilton, A., Johnson, P.D., Jr.: Relations among the fractional chromatic, choice, Hall, and Hall-condition numbers of simple graphs. Discret. Math. 241(1\u20133), 189\u2013199 (2001)","journal-title":"Discret. Math."},{"key":"164_CR6","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1007\/s00493-020-4223-9","volume":"40","author":"Z Dvo\u0159\u00e1k","year":"2020","unstructured":"Dvo\u0159\u00e1k, Z., Ossona de Mendez, P., Wu, H.: 1-subdivisions, the fractional chromatic number and the Hall ratio. Combinatorica 40, 759\u2013774 (2020)","journal-title":"Combinatorica"},{"issue":"1","key":"164_CR7","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/17M115918X","volume":"33","author":"DG Harris","year":"2019","unstructured":"Harris, D.G.: Some results on chromatic number as a function of triangle count. SIAM J. Discret. Math. 33(1), 546\u2013563 (2019)","journal-title":"SIAM J. Discret. Math."},{"key":"164_CR8","doi-asserted-by":"crossref","unstructured":"Janzer, B., Steiner, R., Sudakov, B.: Chromatic number and regular subgraphs. arXiv preprint arXiv:2410.02437, (2024)","DOI":"10.1093\/imrn\/rnae171"},{"issue":"14","key":"164_CR9","doi-asserted-by":"publisher","first-page":"4746","DOI":"10.1016\/j.disc.2008.05.049","volume":"309","author":"PD Johnson Jr","year":"2009","unstructured":"Johnson, P.D., Jr.: The fractional chromatic number, the Hall ratio, and the lexicographic product. Discret. Math. 309(14), 4746\u20134749 (2009)","journal-title":"Discret. Math."},{"issue":"3","key":"164_CR10","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0097-3165(78)90022-5","volume":"25","author":"L Lov\u00e1sz","year":"1978","unstructured":"Lov\u00e1sz, L.: Kneser\u2019s conjecture, chromatic number, and homotopy. J. Comb. Theory Ser. A 25(3), 319\u2013324 (1978)","journal-title":"J. Comb. Theory Ser. A"},{"key":"164_CR11","volume-title":"Fractional Graph Theory: a Rational Approach to the Theory of Graphs","author":"ER Scheinerman","year":"2011","unstructured":"Scheinerman, E.R., Ullman, D.H.: Fractional Graph Theory: a Rational Approach to the Theory of Graphs. Dover publications Inc., New York (2011)"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00164-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-025-00164-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00164-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T23:21:16Z","timestamp":1757460076000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-025-00164-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,4]]},"references-count":11,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["164"],"URL":"https:\/\/doi.org\/10.1007\/s00493-025-00164-0","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2025,7,4]]},"assertion":[{"value":"25 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 July 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"37"}}