{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T07:47:58Z","timestamp":1790668078696,"version":"4.1.0"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We introduce a new method for computing bounds on the independence number and fractional chromatic number of classes of graphs with local constraints and apply this method in various scenarios. We establish a formula that generates a general upper bound for the fractional chromatic number of triangle-free graphs of maximum degree $\\Delta \\ge 3$. This upper bound matches that deduced from the fractional version of Reed's bound for small values of $\\Delta$, and improves it when $\\Delta\\ge 17$, transitioning smoothly to the best possible asymptotic regime, barring a breakthrough in Ramsey theory. Focusing on smaller values of $\\Delta$, we also demonstrate that every graph of girth at least $7$ and maximum degree $\\Delta$ has fractional chromatic number at most $1+ \\min_{k \\in \\mathbb{N}} \\frac{2\\Delta + 2^{k-3}}{k}$. In particular, the fractional chromatic number of a graph of girth $7$ and maximum degree $\\Delta$ is at most $\\frac{2\\Delta+9}{5}$ when $\\Delta \\in [3,8]$, at most $\\frac{\\Delta+7}{3}$ when $\\Delta \\in [8,20]$, at most $\\frac{2\\Delta+23}{7}$ when $\\Delta \\in [20,48]$, and at most $\\frac{\\Delta}{4}+5$ when $\\Delta \\in [48,112]$. In addition, we also obtain new lower bounds on the independence ratio of graphs of maximum degree $\\Delta \\in \\{3,4,5\\}$ and girth $g\\in \\{6,\\dotsc,12\\}$, notably $1\/3$ when $(\\Delta,g)=(4,10)$ and $2\/7$ when $(\\Delta,g)=(5,8)$.<\/jats:p>","DOI":"10.1137\/20m1382283","type":"journal-article","created":{"date-parts":[[2021,11,23]],"date-time":"2021-11-23T13:20:34Z","timestamp":1637673634000},"page":"2815-2843","source":"Crossref","is-referenced-by-count":6,"title":["Fractional Chromatic Number, Maximum Degree, and Girth"],"prefix":"10.1137","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1392-9623","authenticated-orcid":true,"given":"Fran\u00e7ois","family":"Pirot","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jean-S\u00e9bastien","family":"Sereni","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,11,23]]},"reference":[{"key":"atypb1","first-page":"237","volume":"26","author":"Bajnok B.","year":"1998","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"atypb2","first-page":"114","volume":"10","author":"Berge C.","year":"1961","journal-title":"Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.37236\/1386"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.2307\/2043545"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1017\/S030500410002168X"},{"key":"atypb6","first-page":"7","author":"van Batenburg W. Cames","year":"2020","journal-title":"Adv. Combin."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2006.164.51"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20945"},{"key":"atypb9","unstructured":"E. Davies, R. J. Kang, F. Pirot, and J.S. Sereni,\n                      Graph Structure via Local Occupancy\n                      , preprint,https:\/\/arxiv.org\/abs\/2003.14361, 2020."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/jdt085"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1947-08785-1"},{"key":"atypb12","first-page":"463","volume":"2","author":"Erd\u00f6s P.","year":"1935","journal-title":"Compos. Math."},{"key":"atypb13","unstructured":"G. Exoo and R. Jajcay,\n                      Dynamic cage survey\n                      , Elec. J. Combin., Dynamic Surveys (2013), DS16."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1043"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3236-x"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90058-3"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/100812082"},{"key":"atypb18","unstructured":"A. D. King,\n                      Claw-Free Graphs and Two Conjectures on $\\omega$, $\\Delta$, and $\\chi$\n                      , Ph.D. thesis, McGill University, 2009."},{"key":"atypb19","first-page":"679","author":"Kostochka A. V.","year":"1978","journal-title":"New York"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2018.06.007"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"M. Molloy and B. A. Reed,\n                      Graph Colouring and the Probabilistic Method\n                      , Algorithms Combin. 23, Springer-Verlag, Berlin, 2002.","DOI":"10.1007\/978-3-642-04016-0"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"F. P. Ramsey,\n                      On a problem of formal logic\n                      , Proc. London Math. Soc., s2-30 (1930), pp. 264-286.","DOI":"10.1112\/plms\/s2-30.1.264"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90273-X"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90080-4"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1979-0546922-6"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1382283","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:06:52Z","timestamp":1787317612000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1382283"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1382283"],"URL":"https:\/\/doi.org\/10.1137\/20m1382283","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}