{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T16:30:45Z","timestamp":1720715445091},"reference-count":13,"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>A proper k<\/jats:italic>\u2010coloring of a graph is a function such that , for every . The chromatic number is the minimum k<\/jats:italic> such that there exists a proper k<\/jats:italic>\u2010coloring of G<\/jats:italic>. Given a spanning subgraph H<\/jats:italic> of G<\/jats:italic>, a q<\/jats:italic>\u2010backbone k<\/jats:italic>\u2010coloring of is a proper k<\/jats:italic>\u2010coloring c<\/jats:italic> of such that , for every edge . The q<\/jats:italic>\u2010backbone chromatic number is the smallest k<\/jats:italic> for which there exists a q<\/jats:italic>\u2010backbone k<\/jats:italic>\u2010coloring of . In this work, we show that every connected graph G<\/jats:italic> has a spanning tree T<\/jats:italic> such that , and that this value is the best possible. As a direct consequence, we get that every connected graph G<\/jats:italic> has a spanning tree T<\/jats:italic> for which , if , or , otherwise. Thus, by applying the Four Color Theorem, we have that every connected nonbipartite planar graph G<\/jats:italic> has a spanning tree T<\/jats:italic> such that . This settles a question by Wang, Bu, Montassier, and Raspaud (J Combin Optim 23(1) (2012), 79\u201393), and generalizes a number of previous partial results to their question.<\/jats:p>","DOI":"10.1002\/jgt.22108","type":"journal-article","created":{"date-parts":[[2016,11,28]],"date-time":"2016-11-28T08:02:51Z","timestamp":1480320171000},"page":"808-813","source":"Crossref","is-referenced-by-count":1,"title":["On the Existence of Tree Backbones that Realize the Chromatic Number on a Backbone Coloring"],"prefix":"10.1002","volume":"85","author":[{"given":"J.","family":"Araujo","sequence":"first","affiliation":[{"name":"PARGO GROUP\u2014PARALLELLISM GRAPHS AND OPTIMIZATION DEPARTAMENTO DE MATEM\u00c1TICA UNIVERSIDADE FEDERAL DO CEAR\u00c1, FORTALEZA, BRAZIL"}]},{"given":"A. A.","family":"Cezar","sequence":"additional","affiliation":[{"name":"PARGO GROUP\u2014PARALLELLISM GRAPHS AND OPTIMIZATION DEPARTAMENTO DE MATEM\u00c1TICA UNIVERSIDADE FEDERAL DO CEAR\u00c1, FORTALEZA, BRAZIL"}]},{"given":"A.","family":"Silva","sequence":"additional","affiliation":[{"name":"PARGO GROUP\u2014PARALLELLISM GRAPHS AND OPTIMIZATION DEPARTAMENTO DE MATEM\u00c1TICA UNIVERSIDADE FEDERAL DO CEAR\u00c1, FORTALEZA, BRAZIL"}]}],"member":"311","published-online":{"date-parts":[[2016,11,28]]},"reference":[{"key":"e_1_2_3_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-970-5"},{"key":"e_1_2_3_3_1","doi-asserted-by":"crossref","unstructured":"H.Broersma F. V.Fomin P. A.Golovach andG. J.Woeginger Backbone colorings for networks In: Graph\u2010Theoretic Concepts in Computer Science Vol. 2880 of Lecture Notes in Computer Science (H. L. Bodlaender Ed.) Springer Berlin Heidelberg 2003 pp. 131\u2013142.","DOI":"10.1007\/978-3-540-39890-5_12"},{"key":"e_1_2_3_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20228"},{"key":"e_1_2_3_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.02.026"},{"key":"e_1_2_3_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.06.032"},{"key":"e_1_2_3_7_1","doi-asserted-by":"publisher","DOI":"10.1360\/012010-399"},{"key":"e_1_2_3_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.03.003"},{"key":"e_1_2_3_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.01.011"},{"key":"e_1_2_3_10_1","volume-title":"Graph Coloring Problems","author":"Jensen T. R.","year":"1995"},{"key":"e_1_2_3_11_1","doi-asserted-by":"crossref","unstructured":"R.Karp Reducibility among combinatorial problems In: Complexity of Computer Computations (R. Miller J. Thatcher Ed.) Plenum Press Springer US 1972 pp. 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_3_12_1","volume-title":"Graph Colouring and the Probabilistic Method","author":"Molloy M.","year":"2001"},{"key":"e_1_2_3_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-010-9342-6"},{"issue":"4","key":"e_1_2_3_14_1","first-page":"315","article-title":"Backbone coloring for c\n 5\u2010free planar graphs","volume":"43","author":"Zhang S.\u2010M.","year":"2010","journal-title":"J Math Study"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.22108","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.22108","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.22108","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T03:11:15Z","timestamp":1696561875000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.22108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,28]]},"references-count":13,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["10.1002\/jgt.22108"],"URL":"https:\/\/doi.org\/10.1002\/jgt.22108","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]]}}}