{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,7]],"date-time":"2023-10-07T09:41:40Z","timestamp":1696671700893},"reference-count":11,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2016,11,28]],"date-time":"2016-11-28T00:00:00Z","timestamp":1480291200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2017,8]]},"abstract":"Abstract<\/jats:title>For graphs G<\/jats:italic> and H<\/jats:italic>, an H<\/jats:italic>\u2010coloring of G<\/jats:italic> is a map from the vertices of G<\/jats:italic> to the vertices of H<\/jats:italic> that preserves edge adjacency. We consider the following extremal enumerative question: for a given H<\/jats:italic>, which connected n<\/jats:italic>\u2010vertex graph with minimum degree \u03b4 maximizes the number of H<\/jats:italic>\u2010colorings? We show that for nonregular H<\/jats:italic> and sufficiently large n<\/jats:italic>, the complete bipartite graph is the unique maximizer. As a corollary, for nonregular H<\/jats:italic> and sufficiently large n<\/jats:italic> the graph is the unique k<\/jats:italic>\u2010connected graph that maximizes the number of H<\/jats:italic>\u2010colorings among all k<\/jats:italic>\u2010connected graphs. Finally, we show that this conclusion does not hold for all regular H<\/jats:italic> by exhibiting a connected n<\/jats:italic>\u2010vertex graph with minimum degree \u03b4 that has more \u2010colorings (for sufficiently large q<\/jats:italic> and n<\/jats:italic>) than .<\/jats:p>","DOI":"10.1002\/jgt.22105","type":"journal-article","created":{"date-parts":[[2016,11,28]],"date-time":"2016-11-28T08:08:39Z","timestamp":1480320519000},"page":"780-787","source":"Crossref","is-referenced-by-count":4,"title":["Maximizing H<\/i>\u2010Colorings of Connected Graphs with Fixed Minimum Degree"],"prefix":"10.1002","volume":"85","author":[{"given":"John","family":"Engbers","sequence":"first","affiliation":[{"name":"DEPARTMENT OF MATHEMATICS, STATISTICS AND COMPUTER SCIENCE MARQUETTE UNIVERSITY MILWAUKEE WISCONSIN"}]}],"member":"311","published-online":{"date-parts":[[2016,11,28]]},"reference":[{"issue":"4","key":"e_1_2_4_2_1","doi-asserted-by":"crossref","DOI":"10.37236\/4096","article-title":"Graph homomorphisms between trees","volume":"21","author":"Csikv\u00e1ri P.","year":"2014","journal-title":"Electron J Combin"},{"key":"e_1_2_4_3_1","first-page":"7","article-title":"Coloring graphs with graphs: A survey","volume":"63","author":"Cutler J.","year":"2012","journal-title":"Graph Theory Notes NY"},{"key":"e_1_2_4_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.10.003"},{"key":"e_1_2_4_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21820"},{"key":"e_1_2_4_6_1","doi-asserted-by":"crossref","unstructured":"J.EngbersandD.Galvin ExtremalH\u2010colorings of trees and 2\u2010connected graphs to appear in J Combin Theory Ser B https:\/\/doi.org\/10.1016\/j.jctb.2016.09.009.","DOI":"10.1016\/j.jctb.2016.09.009"},{"key":"e_1_2_4_7_1","doi-asserted-by":"crossref","unstructured":"D.GalvinandP.Tetali On weighted graph homomorphisms Graphs Morphisms and Statistical Physics DIMACS Series in Discrete Mathematics and Theoretical Computer Science 63 2004 pp.97\u2013104.","DOI":"10.1090\/dimacs\/063\/07"},{"key":"e_1_2_4_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004631"},{"key":"e_1_2_4_9_1","unstructured":"L.Sernau Graph operations and upper bounds on graph homomorphism counts http:\/\/arxiv.org\/abs\/1510.01833."},{"key":"e_1_2_4_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)90388-3"},{"key":"e_1_2_4_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990538"},{"key":"e_1_2_4_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/100800415"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.22105","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.22105","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.22105","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T03:11:45Z","timestamp":1696561905000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.22105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,28]]},"references-count":11,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["10.1002\/jgt.22105"],"URL":"https:\/\/doi.org\/10.1002\/jgt.22105","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,28]]}}}