{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:39:17Z","timestamp":1787323157235,"version":"build-2736575974"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"name":"Packard Fellowship"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1855635"],"award-info":[{"award-number":["DMS-1855635"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DGE-1656518"],"award-info":[{"award-number":["DGE-1656518"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["524418"],"award-info":[{"award-number":["524418"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004410","name":"T\u00fcrkiye Bilimsel ve Teknolojik Ara\u015ftirma Kurumu","doi-asserted-by":"publisher","award":["118C009"],"award-info":[{"award-number":["118C009"]}],"id":[{"id":"10.13039\/501100004410","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>Let $P_G(k)$ be the number of proper $k$-colorings of a finite simple graph $G$. Tomescu's conjecture, which was recently solved by Fox, He, and Manners, states that $P_G(k) \\le k!(k-1)^{n-k}$ for all connected graphs $G$ on $n$ vertices with chromatic number $k\\geq 4$. In this paper, we study the same problem with the additional constraint that $G$ is $\\ell$-connected. For $2$-connected graphs $G$, we prove a tight bound $P_G(k) \\le (k-1)!((k-1)^{n-k+1} + (-1)^{n-k})$ and show that equality is only achieved if $G$ is a $k$-clique with an ear attached. For $\\ell \\ge 3$, we prove an asymptotically tight upper bound $ P_G(k) \\le k!(k-1)^{n-\\ell - k + 1} + O((k-2)^n)$ and provide a matching lower bound construction. For the ranges $k \\geq \\ell$ or $\\ell \\geq (k-2)(k-1)+1$ we further find the unique graph maximizing $P_G(k)$. We also consider generalizing $\\ell$-connected graphs to connected graphs with minimum degree $\\delta$.<\/jats:p>","DOI":"10.1137\/19m1306646","type":"journal-article","created":{"date-parts":[[2021,6,24]],"date-time":"2021-06-24T10:34:01Z","timestamp":1624530841000},"page":"1478-1502","source":"Crossref","is-referenced-by-count":4,"title":["Tomescu's Graph Coloring Conjecture for $\\ell$-Connected Graphs"],"prefix":"10.1137","volume":"35","author":[{"given":"John","family":"Engbers","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aysel","family":"Erey","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jacob","family":"Fox","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaoyu","family":"He","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,6,24]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2015.04.021"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.4064\/fm-40-1-42-55"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21820"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22105"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-018-1951-3"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.09.009"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-035-8"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2017.09.028"},{"key":"atypb9","first-page":"489","volume":"9","author":"Erey A.","year":"2018","journal-title":"J. Comb."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2018.10.005"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/063\/07"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22446"},{"key":"atypb13","unstructured":"F. Knox and B. Mohar,\n                      Maximum Number of Colourings\n                      , I. 4\\em-Chromatic Graphs, preprint,https:\/\/arxiv.org\/abs\/1708.01781."},{"key":"atypb14","first-page":"26","author":"Knox F.","year":"2019","journal-title":"II. 5\\em-Chromatic Graphs, Electron. J. Combin."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/pdp041"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.07.002"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.4064\/fm-10-1-96-115"},{"key":"atypb19","unstructured":"A. Sah, M. Sawhney, D. Stoner, and Y. Zhao,\n                      A Reverse Sidorenko Inequality\n                      , preprint,https:\/\/arxiv.org\/abs\/1809.09462."},{"key":"atypb20","unstructured":"I. Tomescu,\n                      Introduction to Combinatorics\n                      , Collets., London, 1975."},{"key":"atypb21","first-page":"1124","volume":"273","author":"Tomescu I.","year":"1971","journal-title":"C. R. Acad. Sci. Paris"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190140111"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190180404"},{"key":"atypb24","unstructured":"D. B. West,\n                      Introduction to Graph Theory\n                      , 2nd ed., Prentice-Hall, New York, 2001."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1306646","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:45:05Z","timestamp":1787319905000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1306646"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M1306646"],"URL":"https:\/\/doi.org\/10.1137\/19m1306646","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}