{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T03:32:15Z","timestamp":1768534335124,"version":"3.49.0"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T00:00:00Z","timestamp":1757289600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T00:00:00Z","timestamp":1757289600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001871","name":"Funda\u00e7 para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["UIDB\/00297\/2020"],"award-info":[{"award-number":["UIDB\/00297\/2020"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005855","name":"Universidade Nova de Lisboa","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005855","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comp. Appl. Math."],"published-print":{"date-parts":[[2026,2]]},"abstract":"Abstract<\/jats:title>\n \n Let\n G<\/jats:italic>\n be a simple connected graph, and\n k<\/jats:italic>\n be a positive integer. The\n k<\/jats:italic>\n th graph power\n \n \n $$G^k$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n of\n G<\/jats:italic>\n is the graph whose vertex set is the vertex set of\n G<\/jats:italic>\n and two distinct vertices are adjacent if and only if their distance in\n G<\/jats:italic>\n is at most\n k<\/jats:italic>\n . The independence number of\n \n \n $$G^k$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is the maximum size of an independent set in\n \n \n $$G^k$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . The chromatic number of\n \n \n $$G^k$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ,\n \n \n $$\\chi (G^k)$$<\/jats:tex-math>\n \n \n \u03c7<\/mml:mi>\n (<\/mml:mo>\n \n G<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , is the smallest number of colors needed to color\n \n \n $$G^k$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n so that the vertices sharing the same color form an independent set of\n \n \n $$G^k$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . In this paper, we study the independence number of\n \n \n $$G^k$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , when\n G<\/jats:italic>\n is a tree, by giving a known lower bound for the number of vertices that a tree must have, assuming a certain independence number of\n \n \n $$G^k$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . As a consequence of our proof, we describe all trees that attain this lower bound. For some of the trees given\n G<\/jats:italic>\n , we also describe a (\n \n \n $$\\chi (G^k)$$<\/jats:tex-math>\n \n \n \u03c7<\/mml:mi>\n (<\/mml:mo>\n \n G<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n )-coloring of\n \n \n $$G^k$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n .\n <\/jats:p>","DOI":"10.1007\/s40314-025-03409-2","type":"journal-article","created":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T09:41:53Z","timestamp":1757410913000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the independence number of graph powers"],"prefix":"10.1007","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2695-9079","authenticated-orcid":false,"given":"Ros\u00e1rio","family":"Fernandes","sequence":"first","affiliation":[]},{"given":"R\u00faben","family":"Palma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,9,8]]},"reference":[{"key":"3409_CR1","doi-asserted-by":"publisher","first-page":"2875","DOI":"10.1016\/j.disc.2019.01.016","volume":"342","author":"A Abiad","year":"2019","unstructured":"Abiad A, Coutinho G, Fiol MA (2019) On the $$k$$-independence number of graphs. Discret Math 342:2875\u20132885","journal-title":"Discret Math"},{"key":"3409_CR2","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/j.endm.2005.05.043","volume":"19","author":"M Beis","year":"2005","unstructured":"Beis M, Duckworth W, Zito M (2005) Large $$k$$-independent sets of regular graphs. Electron Notes Discret Math 19:321\u2013327","journal-title":"Electron Notes Discret Math"},{"key":"3409_CR3","series-title":"Graduate texts in mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0619-4","volume-title":"Modern graph theory","author":"B Bollob\u00e1s","year":"1998","unstructured":"Bollob\u00e1s B (1998) Modern graph theory, vol 184. Graduate texts in mathematics. Springer, New York"},{"key":"3409_CR4","volume-title":"Graph theory","author":"R Diestel","year":"2000","unstructured":"Diestel R (2000) Graph theory. Springer, New York"},{"key":"3409_CR5","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0020-0190(03)00232-1","volume":"87","author":"G Fertin","year":"2003","unstructured":"Fertin G, Godard E, Raspaud A (2003) Acyclic and $$k$$-distance coloring of the grid. Inf Process Lett 87:51\u201358","journal-title":"Inf Process Lett"},{"key":"3409_CR6","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0166-218X(96)00078-9","volume":"75","author":"P Firby","year":"1997","unstructured":"Firby P, Haviland J (1997) Independence and average distance in graphs. Discret Appl Math 75:27\u201337","journal-title":"Discret Appl Math"},{"key":"3409_CR7","doi-asserted-by":"publisher","first-page":"107","DOI":"10.12988\/ijcms.2020.91441","volume":"15","author":"M-J Jou","year":"2020","unstructured":"Jou M-J, Lin J-J, Lin Q-Y (2020) On the 2-independence number of trees. Int J Contemp Math Sci 15:107\u2013112","journal-title":"Int J Contemp Math Sci"},{"key":"3409_CR8","unstructured":"Koerts HO (2021) On the $$k$$-independent set problem. Bachelor thesis, Eindhoven University of Technology"},{"key":"3409_CR9","first-page":"47","volume":"95","author":"MC Kong","year":"1993","unstructured":"Kong MC, Zhao Y (1993) On computing maximum $$k$$-independent sets. Congr Numer 95:47\u201360","journal-title":"Congr Numer"},{"issue":"2","key":"3409_CR10","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/j.akcej.2017.11.007","volume":"16","author":"PK Niranjan","year":"2019","unstructured":"Niranjan PK, Kola SR (2019) The k-distance chromatic number of trees and cycles. AKCE Int J Graphs Comb 16(2):230\u2013235","journal-title":"AKCE Int J Graphs Comb"},{"key":"3409_CR11","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/s00373-020-02244-y","volume":"37","author":"S O","year":"2021","unstructured":"O S, Shi Y, Taoqiu Z (2021) Sharp upper bounds on the $$k$$-independence number in graphs with given minimum and maximum degree. Graphs Comb 37:393\u2013408","journal-title":"Graphs Comb"}],"container-title":["Computational and Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40314-025-03409-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s40314-025-03409-2","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40314-025-03409-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T05:31:43Z","timestamp":1768368703000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s40314-025-03409-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,8]]},"references-count":11,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["3409"],"URL":"https:\/\/doi.org\/10.1007\/s40314-025-03409-2","relation":{},"ISSN":["2238-3603","1807-0302"],"issn-type":[{"value":"2238-3603","type":"print"},{"value":"1807-0302","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,8]]},"assertion":[{"value":"12 May 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 August 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 August 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 September 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"No potential conflict of interest was reported by the authors.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"22"}}