{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:08Z","timestamp":1740109328252,"version":"3.37.3"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2023,4,13]],"date-time":"2023-04-13T00:00:00Z","timestamp":1681344000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,4,13]],"date-time":"2023-04-13T00:00:00Z","timestamp":1681344000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,11]]},"DOI":"10.1007\/s00453-023-01120-4","type":"journal-article","created":{"date-parts":[[2023,4,13]],"date-time":"2023-04-13T07:14:54Z","timestamp":1681370094000},"page":"3406-3429","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of L(p,\u00a0q)-Edge-Labelling"],"prefix":"10.1007","volume":"85","author":[{"given":"Ga\u00e9tan","family":"Berthe","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4642-8614","authenticated-orcid":false,"given":"Barnaby","family":"Martin","sequence":"additional","affiliation":[]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[]},{"given":"Siani","family":"Smith","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,13]]},"reference":[{"key":"1120_CR1","first-page":"175","volume":"13174","author":"G Berthe","year":"2022","unstructured":"Berthe, G., Martin, B., Paulusma, D., Smith, S.: The complexity of L(p, q)-edge-labelling. Proc. WALCOM 2022. LNCS 13174, 175\u2013186 (2022)","journal-title":"LNCS"},{"key":"1120_CR2","first-page":"18","volume":"12730","author":"J Bok","year":"2021","unstructured":"Bok, J., Jedlickov\u00e1, N., Martin, B., Paulusma, D., Smith, S.: Injective colouring for $${H}$$-free graphs. Proc. CSR 2021. LNCS 12730, 18\u201330 (2021)","journal-title":"LNCS"},{"key":"1120_CR3","unstructured":"Bok, J., Jedlic\u0306kov\u00e1, N., Martin, B., Paulusma, D., Smith, S.: Acyclic, star and injective colouring: A complexity picture for H-free graphs. Proc. ESA 2020, LIPIcs 173, 22:1\u201322:22 (2020)"},{"issue":"2","key":"1120_CR4","doi-asserted-by":"publisher","first-page":"P2.43","DOI":"10.37236\/10738","volume":"29","author":"C Brause","year":"2022","unstructured":"Brause, C., Golovach, P.A., Martin, B., Paulusma, D., Smith, S.: Acyclic, star, and injective colouring: Bounding the diameter. Electron. J. Comb. 29(2), P2.43 (2022)","journal-title":"Electron. J. Comb."},{"key":"1120_CR5","doi-asserted-by":"publisher","first-page":"1344","DOI":"10.1093\/comjnl\/bxr037","volume":"54","author":"T Calamoneri","year":"2011","unstructured":"Calamoneri, T.: The $${L}(h, k)$$-labelling problem: an updated survey and annotated bibliography. Comput. J. 54, 1344\u20131371 (2011)","journal-title":"Comput. J."},{"key":"1120_CR6","first-page":"294","volume":"5125","author":"J Fiala","year":"2008","unstructured":"Fiala, J., Golovach, P.A., Kratochv\u00edl, J.: Computational complexity of the distance constrained labeling problem for trees (extended abstract). Proc. ICALP 2008. LNCS 5125, 294\u2013305 (2008)","journal-title":"LNCS"},{"key":"1120_CR7","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0166-218X(00)00387-5","volume":"113","author":"J Fiala","year":"2001","unstructured":"Fiala, J., Kloks, T., Kratochv\u00edl, J.: Fixed-parameter complexity of lambda-labelings. Discret. Appl. Math. 113, 59\u201372 (2001)","journal-title":"Discret. Appl. Math."},{"key":"1120_CR8","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1137\/0405048","volume":"5","author":"JR Griggs","year":"1992","unstructured":"Griggs, J.R., Yeh, R.K.: Labelling graphs with a condition at distance 2. SIAM J. Discret. Math. 5, 586\u2013595 (1992)","journal-title":"SIAM J. Discret. Math."},{"key":"1120_CR9","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/S0012-365X(01)00466-6","volume":"256","author":"G Hahn","year":"2002","unstructured":"Hahn, G., Kratochv\u00edl, J., \u0160ir\u00e1\u0148, J., Sotteau, D.: On the injective chromatic number of graphs. Discret. Math. 256, 179\u2013192 (2002)","journal-title":"Discret. Math."},{"key":"1120_CR10","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10, 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"key":"1120_CR11","doi-asserted-by":"publisher","first-page":"3270","DOI":"10.1016\/j.disc.2008.09.028","volume":"309","author":"R Janczewski","year":"2009","unstructured":"Janczewski, R., Kosowski, A., Ma\u0142afiejski, M.: The complexity of the $${L}(p, q)$$-labeling problem for bipartite planar graphs of small degree. Discret. Math. 309, 3270\u20133279 (2009)","journal-title":"Discret. Math."},{"key":"1120_CR12","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.dam.2017.01.007","volume":"246","author":"D Knop","year":"2018","unstructured":"Knop, D., Masar\u00edk, T.: Computational complexity of distance edge labeling. Discret. Appl. Math. 246, 80\u201398 (2018)","journal-title":"Discret. Appl. Math."},{"key":"1120_CR13","first-page":"71","volume":"1992","author":"EL Lloyd","year":"1992","unstructured":"Lloyd, E.L., Ramanathan, S.: On the complexity of distance-$$2$$ coloring. Proc. ICCI 1992, 71\u201374 (1992)","journal-title":"Proc. ICCI"},{"key":"1120_CR14","unstructured":"Lov\u00e1sz, L.: Coverings and coloring of hypergraphs. Proc. 4th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, 1973), Congressus Numerantium, VIII, 3\u201312 (1973)"},{"key":"1120_CR15","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0166-218X(01)00237-2","volume":"118","author":"M Mahdian","year":"2002","unstructured":"Mahdian, M.: On the computational complexity of strong edge coloring. Discret. Appl. Math. 118, 239\u2013248 (2002)","journal-title":"Discret. Appl. Math."},{"key":"1120_CR16","unstructured":"Masar\u00edk, T.: Private communication (2020)"},{"key":"1120_CR17","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF02592052","volume":"26","author":"S McCormick","year":"1983","unstructured":"McCormick, S.: Optimal approximation of sparse hessians and its equivalence to a graph coloring problem. Math. Progr. 26, 153\u2013171 (1983)","journal-title":"Math. Progr."},{"key":"1120_CR18","first-page":"216","volume":"1978","author":"TJ Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. STOC 1978, 216\u2013226 (1978)","journal-title":"STOC"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01120-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01120-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01120-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,31]],"date-time":"2023-10-31T19:03:06Z","timestamp":1698778986000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01120-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,13]]},"references-count":18,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["1120"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01120-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2023,4,13]]},"assertion":[{"value":"13 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 April 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}