{"entities":{"Q5948961":{"pageid":8125763,"ns":120,"title":"Item:Q5948961","lastrevid":47703637,"modified":"2026-01-02T11:47:01Z","type":"item","id":"Q5948961","labels":{"en":{"language":"en","value":"Fixed-parameter complexity of \\(\\lambda\\)-labelings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1672486"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$5801F5AF-C31A-479A-90A5-642AE0E5E983","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c34a1ad274d8a808607c751b29103cd24460e728","datavalue":{"value":{"text":"Fixed-parameter complexity of \\(\\lambda\\)-labelings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5948961$C3232C01-72B8-4EF0-8852-DE627CF343EC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"01ab43dbb13c81b9e5a5ce3deaba5be08fba7d05","datavalue":{"value":"0982.05085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5948961$DD5B03D3-5C3C-407E-95AC-F0511F81B7E2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7bb4685e30276c6130720a1e79dc108bff3b2496","datavalue":{"value":"10.1016/S0166-218X(00)00387-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5948961$900DBDEE-7A03-4B49-ADA0-75BC35F1C8F6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d64412fd76b8eb7263aefd3e70a618ba1acaca17","datavalue":{"value":{"entity-type":"item","numeric-id":190515,"id":"Q190515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$6F31D444-DEF3-4FD1-A1F9-45650F089630","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d8e7715a2f78d23e9e49bdcad66cde6bee1dec62","datavalue":{"value":{"entity-type":"item","numeric-id":190505,"id":"Q190505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$A50E4C2B-1ECB-4AE1-B038-A7A3068FDCCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9034d743abb2e8189da1fd67afac14b0cf3088f3","datavalue":{"value":{"entity-type":"item","numeric-id":175587,"id":"Q175587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$05BCF467-F515-443C-8255-89F9BA9085E1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$34DCECFE-F6B4-48E7-8DAE-5D219E9CAAC0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2d523614f519ec0feabed1eeb5eb67171dc8b190","datavalue":{"value":{"time":"+2002-03-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5948961$C4538EB8-D28B-4C96-8F3E-5336A6B01B31","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2bdecdbc4a2f445476fc7f3ff8f65172d6288c74","datavalue":{"value":"A \\(\\lambda (p,q)\\) labelling of a graph \\(G=(V,E)\\) is an assignment of non-negative integers to the vertices in \\(V\\), such that adjacent vertices get labels that differ by at least \\(p\\), and vertices of distance two in \\(G\\) get labels that differ by at least \\(q\\). \\(L(G;p,q)\\) is the minimum possible maximum value in a \\(\\lambda (p,q)\\) labelling of \\(G\\). The standard \\(\\lambda\\)-coloring problem is to determine \\(L(G;2,1)\\) of a graph. This paper shows that this problem is solvable in polynomial time on almost \\(k\\)-trees (graphs that can be formed by adding \\(k\\) edges to a tree), and is NP-hard for every fixed maximum label value. It is also shown for all values \\(p>q\\geq 1\\) that there are several \\(\\lambda\\) such that deciding if \\(L(G;p,q) \\leq \\lambda\\) is NP-complete (taking \\(\\lambda\\) here as fixed part of the problem description). Some other related results are also shown.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5948961$247A645C-A6FB-4F0C-88F9-E525007F1860","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eea1ea35de576c62b8101835521aa928ecd629a1","datavalue":{"value":{"entity-type":"item","numeric-id":242851,"id":"Q242851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$5794F4BB-1F08-420F-876D-9A47FC0AB777","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5948961$CB02356B-05D3-4450-A230-4AA665F0818C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5948961$F9701D74-F573-4D15-A490-9A1A179353FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"239a4a174af03c82b61364f762873d53ef0a37ef","datavalue":{"value":"05C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5948961$C12CFDD1-9CC7-445F-B522-9BD03D40CA4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5948961$00B75980-E5FC-4D28-9C52-9AB1C753FB65","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3679200659f140e30efb2e0f7442bed1f2d70bfa","datavalue":{"value":"1672486","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5948961$1F00668A-2B25-4301-917A-7205ABD85E4E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b975715e760da62f784950c39d59a770a763afa","datavalue":{"value":"graph cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q5948961$02592F0E-3A02-4448-A955-729CC6E792DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77ace25a638e56e6fa7da46ca9b6aaa0863b538d","datavalue":{"value":"channel assignment","type":"string"},"datatype":"string"},"type":"statement","id":"Q5948961$1B9D5713-F615-4BD3-B46D-046C1C7D8BB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a594ef9dbe8a090d158483294abcbc56f4589f9b","datavalue":{"value":"graph labeling","type":"string"},"datatype":"string"},"type":"statement","id":"Q5948961$7AE410E9-6626-4891-A4B7-E0C39234B665","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a679f7296673bdfcb298ff38818ae3775df2b07c","datavalue":{"value":"fixed parameter complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5948961$4F2CB07E-89C6-4963-8960-A2ED7706ADF8","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"f17cee38f3d36baf977b9480328facbca36f6d4a","datavalue":{"value":"Q56505203","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5948961$4A412EBB-D35B-4308-8576-44A6FCF01A71","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$8A5E57FB-E8EC-43DC-878E-07654FFCBB7D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8213a6dc1fa284bfdedde71b2fc35e745595f18","datavalue":{"value":{"entity-type":"item","numeric-id":4017175,"id":"Q4017175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$E7043F1A-DB15-448E-8B28-9E00ACC39F1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a026cd0f4b7a301bb63b3a31e47f3cb40412d167","datavalue":{"value":{"entity-type":"item","numeric-id":4881295,"id":"Q4881295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$86B903CB-360B-4BA8-AC0E-DE5A23C87C74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15f66b4844bcb79a520b665f58fdec673994d537","datavalue":{"value":{"entity-type":"item","numeric-id":4393480,"id":"Q4393480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$B3B3F0AC-B851-464A-9C89-1E6A040C737A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54164d6ccb29174849addc3d3fec5a7bb9ee64cc","datavalue":{"value":{"entity-type":"item","numeric-id":4232883,"id":"Q4232883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$C4A144BE-0133-4118-AC45-CDDAAB81E471","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a359527ed469944dfb2b879452c1c42adfdac53","datavalue":{"value":{"entity-type":"item","numeric-id":4879166,"id":"Q4879166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$FAE92978-7C93-4DD0-89AF-834B191E4F65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06620ceef76e9c1a994d88976c9f13d26ac05485","datavalue":{"value":{"entity-type":"item","numeric-id":1343254,"id":"Q1343254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$9A3D72AC-1E10-45B9-9914-E7B6BABE2FE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30315663020f3964456f9315ac887932c8442495","datavalue":{"value":{"entity-type":"item","numeric-id":4940090,"id":"Q4940090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$3B8FB964-D5F5-4D90-9E9D-5C5663ACF04A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a415e76a6c4dfffab8c5043c692bae1e05da99b","datavalue":{"value":{"entity-type":"item","numeric-id":4030197,"id":"Q4030197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$655522B0-99E1-4C7B-B76B-C9A1DCFADF06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4e9c7040a510a4a56a7f3a400944ca0685c5831","datavalue":{"value":{"entity-type":"item","numeric-id":4242956,"id":"Q4242956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$F7E56344-D303-4E80-A7A9-44A55DF2A8F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d605beb910baf805d1b163189ed772d208f616ab","datavalue":{"value":{"entity-type":"item","numeric-id":1336698,"id":"Q1336698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$C497FA36-D79F-4F9C-B145-2A6007FDAE7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3967edc017f7adb84a083b9015af85c3ea4b9615","datavalue":{"value":{"entity-type":"item","numeric-id":1386472,"id":"Q1386472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$FDF65557-758F-45E6-9A25-CFDAC6A11EE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18b78bdc859d05de62ccc9792c29fa6a100ccb0b","datavalue":{"value":{"entity-type":"item","numeric-id":4373685,"id":"Q4373685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$8344C814-A52F-4AE2-AEFA-A8DD0CC6A343","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc342e5f91538c992b7030456482406e49c79a46","datavalue":{"value":{"entity-type":"item","numeric-id":4223772,"id":"Q4223772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$96920CFB-47AA-4B02-A298-EE16931FAF3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36f5833550e269623349e512f5f9ffd53bbcd5fc","datavalue":{"value":{"entity-type":"item","numeric-id":4385515,"id":"Q4385515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$3E20243D-4376-44E6-AF8B-C3E435BB0A3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d409c055020774d249d6a81979768128839bba90","datavalue":{"value":{"entity-type":"item","numeric-id":4764347,"id":"Q4764347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$FC85E0AD-D301-4081-9E08-047E3FA81179","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6091596b08b7d59e38226a0506e4b5e8f68bd694","datavalue":{"value":{"entity-type":"item","numeric-id":4940064,"id":"Q4940064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$8E5FF9BA-E22D-40FF-8BAA-E81EADA99CCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c928b2e6f60b8549341fdb3b8bf959833ccbbdcd","datavalue":{"value":{"entity-type":"item","numeric-id":4287946,"id":"Q4287946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$EA95F71E-D066-436F-BAA5-1A4E7B13AD2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c0bdc13b7ae115bf84ac5dc224b0b308b85c2c7","datavalue":{"value":{"entity-type":"item","numeric-id":4863972,"id":"Q4863972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5948961$976995E9-279E-450F-9B1E-641375A55931","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ebd943eb69cb28cc3c96cd6b4f45cc598db39d50","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(00)00387-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q5948961$9E616C3F-09CC-4B60-9F67-7ABF44F90A40","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"87150697a245097cbd065cd4a523c6991e92c4cd","datavalue":{"value":"W2184661648","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5948961$E6F8C5D1-96AB-4C7D-83BC-9DC205D3B024","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"846f5f864350097a342d9c65ac2f33c7420942e4","datavalue":{"value":"journals/dam/FialaKK01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5948961$E0FFE326-B19A-45AC-A851-81D16DD53A04","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa1aad06d22a480b0a8ecfb32724591fc826d98f","datavalue":{"value":{"entity-type":"item","numeric-id":4944992,"id":"Q4944992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57d21aefc59b7ce750dbe400a8ec1da43c454084","datavalue":{"value":{"amount":"+0.969173789024353","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5948961$60B524F9-96C5-46A1-8AB6-8E7011D5E874","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"faede22e16935c1551653f78e29a87500861ec2c","datavalue":{"value":{"entity-type":"item","numeric-id":4448371,"id":"Q4448371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57d21aefc59b7ce750dbe400a8ec1da43c454084","datavalue":{"value":{"amount":"+0.969173789024353","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5948961$AFA95570-36BE-44C0-9C19-4EED00199038","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fe7e30c6817a23912ab35586ef98328221e055f","datavalue":{"value":{"entity-type":"item","numeric-id":4030197,"id":"Q4030197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ecd09ddacdd026f5131a1b62bf112d7e4c831e2d","datavalue":{"value":{"amount":"+0.8517783880233765","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5948961$E62CB75F-1C45-48EA-8D92-CD9BB2EBEEBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ee7eb039438f9e6451f5c3d8c79f93d28de6bba","datavalue":{"value":{"entity-type":"item","numeric-id":3521928,"id":"Q3521928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb730bef12cce9dbb51ec66dfded19c0c01f3ded","datavalue":{"value":{"amount":"+0.8504263758659363","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5948961$B20A2D72-193D-4C4F-AC03-21FCE3DE53E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38a78344298faface95e5b036a15231297cb1258","datavalue":{"value":{"entity-type":"item","numeric-id":4881295,"id":"Q4881295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"912c3d4e268d812d692e4ba79e2a7b9f98a1bc10","datavalue":{"value":{"amount":"+0.8470897674560547","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5948961$2227AD68-8A06-4514-AFBF-FE823CE2FBD1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5948961","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5948961"}}}}}