{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:05:24Z","timestamp":1787321124932,"version":"build-2736575974"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["DEC-2017\/25\/N\/ST1\/00459"],"award-info":[{"award-number":["DEC-2017\/25\/N\/ST1\/00459"]}],"id":[{"id":"10.13039\/501100004281","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>For a graph $G$, $L(G)^t$ is the $t$th power of the line graph of $G$; that is, vertices of $L(G)^t$ are edges of $G$ and two edges $e,f\\in E(G)$ are adjacent in $L(G)^t$ if $G$ contains a path with at most $t$ vertices that starts in a vertex of $e$ and ends in a vertex of $f$. The distance-$t$ chromatic index of $G$ is the chromatic number of $L(G)^t$, and a $t$-strong clique in $G$ is a clique in $L(G)^t$. Finding upper bounds for the distance-$t$ chromatic index and $t$-strong clique are problems related to two famous problems: the conjecture of Erd\u00f6s and Ne\u0161et\u0159il concerning the strong chromatic index, and the degree\/diameter problem. We prove that the size of a $t$-strong clique in a graph with maximum degree $\\Delta$ is at most $1.75\\Delta^t+O\\left(\\Delta^{t-1}\\right)$, and for bipartite graphs the upper bound is at most $\\Delta^t+O\\left(\\Delta^{t-1}\\right)$. As a corollary, we obtain upper bounds of $1.881\\Delta^t +O\\left(\\Delta^{t-1}\\right)$ and $1.9703+O\\left(\\Delta^{t-1}\\right)$ on the distance-$t$ chromatic index of bipartite graphs and general graphs. We also show results for some special classes of graphs: $K_{1,r}$-free graphs and graphs with a large girth.<\/jats:p>","DOI":"10.1137\/21m1406970","type":"journal-article","created":{"date-parts":[[2021,12,16]],"date-time":"2021-12-16T10:23:38Z","timestamp":1639650218000},"page":"3017-3029","source":"Crossref","is-referenced-by-count":0,"title":["$t$-Strong Cliques and the Degree-Diameter Problem"],"prefix":"10.1137","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9606-6052","authenticated-orcid":true,"given":"Micha\u0142","family":"De\u0345bski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ma\u0142gorzata","family":"\u015aleszy\u0144ska-Nowak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,12,16]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90678-9"},{"key":"atypb2","unstructured":"M. Bonamy, T. Perrett, and L. Postle,\n                      Colouring Graphs with Sparse Neighbourhoods: Bounds and Applications\n                      , preprint,https:\/\/arxiv.org\/abs\/1810.06704, 2018."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2015.06.038"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.03.008"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"W. Cames van Batenburg, R. de Joannis de Verclos, R. J. Kang, and F. Pirot,\n                      Strong Chromatic Index and Hadwiger Number\n                      , preprint,https:\/\/arxiv.org\/abs\/1905.06031, 2021.","DOI":"10.1002\/jgt.22788"},{"key":"atypb6","first-page":"64","volume":"31","author":"Cames van Batenburg W.","year":"2020","journal-title":"S.)"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22700"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.03.053"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21716"},{"key":"atypb10","first-page":"1057","volume":"88","author":"De\u0345bski M.","year":"2019","journal-title":"S.)"},{"key":"atypb11","first-page":"162","author":"Erd\u00f6s P.","year":"1989","journal-title":"Springer"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22452"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90163-5"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.37236\/7016"},{"key":"atypb15","unstructured":"E. Hurley, R. de Joannis de Verclos, and R. J. Kang,\n                      An Improved Procedure for Colouring Graphs of Bounded Local Density\n                      , preprint,https:\/\/arxiv.org\/abs\/2007.07874, 2020."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548313000473"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.07.001"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/15M1035422"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548318000068"},{"issue":"2","key":"atypb20","doi-asserted-by":"crossref","first-page":"S14","DOI":"10.37236\/2425","volume":"20","author":"Miller M.","year":"2013","journal-title":"Electron. J. Combin."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1724"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"M. Molloy and B. Reed,\n                      Graph Colouring and the Probabilistic Method\n                      , Springer, Berlin, 2002.","DOI":"10.1007\/978-3-642-04016-0"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199804)27:4<177::AID-JGT1>3.0.CO;2-K"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2016.01.003"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1406970","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:07:25Z","timestamp":1787317645000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1406970"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/21M1406970"],"URL":"https:\/\/doi.org\/10.1137\/21m1406970","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}