{"entities":{"Q2384400":{"pageid":2395143,"ns":120,"title":"Item:Q2384400","lastrevid":72669183,"modified":"2026-04-14T06:24:33Z","type":"item","id":"Q2384400","labels":{"en":{"language":"en","value":"An extremal problem on non-full colorable graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5194358"}},"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":"Q2384400$6107EBF4-4EF6-44E2-9DB2-25506B6F2AB2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c20f6050d2ae8f53ba5b16e3b5853201a44e89b6","datavalue":{"value":{"text":"An extremal problem on non-full colorable graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2384400$9319C4E2-053B-4DC8-89C5-3CAE4508C440","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b18fe2e9cdb7484a3a84917abf97128f08170966","datavalue":{"value":"1125.05091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2384400$3646494A-56EE-42DC-82D8-3E1D2A64F3C1","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":"Q2384400$FF5CCB36-146B-429B-9909-2AD8EDDDDEEF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c48a6c1f155a0551de4d7827de3fb3b9801c8b6f","datavalue":{"value":{"time":"+2007-09-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2384400$BE6F1F92-F238-4A05-B672-A26A3F787EF8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b84ef01597fdbaf0f4ed63cd0e602ca600fb1aed","datavalue":{"value":"For a given graph \\(G\\) of order \\(n(G)\\), a \\(k\\)-\\(L(2,1)\\)-labeling is defined as \\(f: V(G)\\to \\{ 1,2,\\dots,k\\}\\) such that \\(| f(u)-f(v)| \\geq 2\\) when \\(\\text{dist}_G(u,v)=1\\) and \\(| f(u)-f(v)| \\geq 1\\) when \\(\\text{dist}_G(u,v)=2\\). The \\(L(2,1)\\)-labeling number of \\(G\\), \\(\\lambda (G)\\), is the smallest number \\(k\\) such that \\(G\\) has a \\(k\\)-\\(L(2,1)\\)-labeling. The hole index \\(\\rho (G)\\) of \\(G\\) is the minimum number of integers not used in a \\(\\lambda (G)\\)-\\(L(2,1)\\)-labeling of \\(G\\). Graphs with \\(\\lambda (G)=2m\\) and \\(\\rho (G)=m\\) for a positive integer \\(m\\) are considered in the paper. A graph \\(G\\) belongs to the family \\(G(k,m)\\) if and only if \\(G\\) is \\((m+1)\\)-partite with \\(V(G)=V_0\\cup V_1\\cup\\dots\\cup V_m\\) where \\(| V_0| =| V_1| =\\dots =| V_m| =k\\) and for every \\(0\\leq i<j\\leq m\\) the subgraph induced on \\(V_i\\cup V_j\\) is a perfect matching. It is proved for every integer \\(m\\geq 1\\) that if \\(\\lambda (G)=2m\\) and \\(\\rho (G)=m\\), then \\(G\\in G(k,m)\\) for some integer \\(k\\geq 1\\). Further it is proved that \\(n(G) =2m+1,\\lambda (G)=2m\\), and \\(\\rho (G)=m\\) if and only if \\(G\\in G(2,m)\\). It is also shown that for any \\(k\\geq 3\\) and \\(m\\geq 2\\) there exists a connected graph \\(G\\in G(k,m)\\) with \\(\\lambda (G)=2m\\) and \\(\\rho (G)=0\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2384400$59DF4AD7-A9CC-49F7-B308-518317A96184","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2384400$B5CF188A-1A6D-44A8-BAC4-5972B4065F94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2384400$5407C694-A973-46C1-9F0B-CD4C8CBD2FAD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6e2a377ef8f79fcb7ae1a01f01439bb05b8cc0ce","datavalue":{"value":"5194358","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2384400$E9BEAC7A-A343-4365-BB2C-15BAFD378FB0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d71ff41485748ce2d4eed71a2ccf63f8ea2b3c05","datavalue":{"value":"channel assignment problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2384400$C29CB5B9-251B-4A69-91A4-094642EBC655","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ce9fee220c968fcd34fb784e74884ddff4eeade","datavalue":{"value":"distance-two labeling","type":"string"},"datatype":"string"},"type":"statement","id":"Q2384400$4C915D4D-8CD7-441A-8668-52C34724F6B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1676fd22bd67d79974ef42da57b8a9d2cb02b750","datavalue":{"value":"\\(L(2","type":"string"},"datatype":"string"},"type":"statement","id":"Q2384400$861C2309-BFD8-4608-9262-BE9A0D485033","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c2846d8e2c4a1c01baa64d694cf21ed79a5d7951","datavalue":{"value":"1)\\)-labeling","type":"string"},"datatype":"string"},"type":"statement","id":"Q2384400$8A0BACE4-4E69-4430-A17C-8C57E3A60B63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84b98ede317dcad6706f80faa62e3c2696777499","datavalue":{"value":"no-hole coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2384400$214728A8-75D2-4DC5-AD40-2E9507D901D1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7a16e1e58ef83ee139c1b19d99d1b0144d5d0f30","datavalue":{"value":{"entity-type":"item","numeric-id":511192,"id":"Q511192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2384400$3481BA6F-DA22-49B8-B09C-7C0BFFA75CC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5a14db460f86c1ad9df5fd9c6b0355139b8f82db","datavalue":{"value":{"entity-type":"item","numeric-id":385184,"id":"Q385184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2384400$9264A2E0-BE0C-45AD-80BF-19B3C4D37E06","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"55e284968cff24f9e3e328c51dd86858b1ce4256","datavalue":{"value":{"entity-type":"item","numeric-id":186109,"id":"Q186109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2384400$3313477C-F67B-4310-ABCF-FC3AC17324B4","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":"Q2384400$C3F5743A-DC1D-40F6-BB51-9B3C6E76E4B7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d6bf64db8f5dc9a5188e55933581ad568f88dfdb","datavalue":{"value":"https://doi.org/10.1016/j.dam.2007.05.025","type":"string"},"datatype":"url"},"type":"statement","id":"Q2384400$E9B79AE3-117F-4ACE-89B3-1777151B3592","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"18e717c299e31abee7f5164b4d6750a523cc4286","datavalue":{"value":"W1986471356","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2384400$93210F63-0E98-485E-8E28-691D9D3EDB8D","rank":"normal"}],"P223":[{"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":"Q2384400$EBF79285-20E2-489D-80BF-2BC1DBB7ABF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1863bcb7f080051ae43d0070cae6c50377e89d86","datavalue":{"value":{"entity-type":"item","numeric-id":1408461,"id":"Q1408461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2384400$C5C32D0A-7D72-45B8-84FE-24D348F02241","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2a258d6e4594c690715f103d1fd812d2b837b4a","datavalue":{"value":{"entity-type":"item","numeric-id":3440265,"id":"Q3440265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2384400$BEFC6F07-46EC-4AFF-ABC3-734FEA9D039C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a58f442b8ad164e37eee57bb6fd4df5e4c285be6","datavalue":{"value":{"entity-type":"item","numeric-id":5317610,"id":"Q5317610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2384400$DE55A097-95E1-4C7D-B4AB-2B424E326BF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3e9cc8ab832fae81ec37f6f753c37302712ad49","datavalue":{"value":{"entity-type":"item","numeric-id":1765378,"id":"Q1765378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2384400$68A8A83E-2034-4B88-8B6D-7FEF008FE357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c01c44950b85395be4d65d72ca0c9528f5ea542","datavalue":{"value":{"entity-type":"item","numeric-id":2706187,"id":"Q2706187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2384400$CEDEB4FF-C369-4C2A-901E-E6AC92168FB4","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":"Q2384400$1D97160F-D3D1-4560-BCA8-0688A12BDAA8","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":"Q2384400$59C0A207-A3D5-4148-8002-F28E95AB421A","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":"Q2384400$13AD860D-2FC3-4871-AB99-6D1373A9D2CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a68af48ad999f615b155389b2942cb7f82be99f","datavalue":{"value":{"entity-type":"item","numeric-id":3440271,"id":"Q3440271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2384400$7F86B312-5658-4DE7-956D-A6E884998876","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7d94f86f4b0ec6673ebe63b6ecc9db7e2817d3f","datavalue":{"value":{"entity-type":"item","numeric-id":2370429,"id":"Q2370429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2384400$49F39B03-FCF2-40CF-BE95-56D62230E19F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2ad854e4145ad8fc80246024186064227c61b4e","datavalue":{"value":{"entity-type":"item","numeric-id":2497501,"id":"Q2497501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2384400$B17D3919-E54E-45E4-BA01-EBD67714C39E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"42e44e10e32ffb4c2cb228021ab5cf9d23b195a7","datavalue":{"value":"10.1016/J.DAM.2007.05.025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2384400$728F1175-C771-4F27-B7C1-7CB87E261975","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"760aa5ad7782d98f10b1240d0b5d18442cea13fb","datavalue":{"value":{"entity-type":"item","numeric-id":2081493,"id":"Q2081493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd2eb5a9992fd1b7437c8ec09c48921e1f221db7","datavalue":{"value":{"amount":"+0.8406868577003479","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":"Q2384400$C2B9C268-1F35-4338-8EBD-B1C0AFDEEE19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54c2cefb223bb6b7fb1794e9815446e0cea22ef3","datavalue":{"value":{"entity-type":"item","numeric-id":1408461,"id":"Q1408461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25d7af54bd19c00c50a9f1972af4c0b95810225d","datavalue":{"value":{"amount":"+0.8378202319145203","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":"Q2384400$C96D9E72-7DCD-4B73-BE05-D4CF2A6D4795","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"316a3e50e64a048e88070cd4288d0001d7ebd625","datavalue":{"value":{"entity-type":"item","numeric-id":5317610,"id":"Q5317610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7104000026c920908186e08334f1886912285274","datavalue":{"value":{"amount":"+0.8349037170410156","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":"Q2384400$AF664125-3D0D-40E1-B02E-6E0DC0466B6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bf34634eafa9eb43030ada14cf2770fda8c2511","datavalue":{"value":{"entity-type":"item","numeric-id":3171038,"id":"Q3171038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec4b4cc23556e8b880ccc2d321b1e77d88ba9c70","datavalue":{"value":{"amount":"+0.81675124168396","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":"Q2384400$FBEBBC94-A902-4FA9-BA43-D589B29463C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bcf57aeb475341593edf232a2b692afa88879bd","datavalue":{"value":{"entity-type":"item","numeric-id":3009237,"id":"Q3009237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0125098c7ee9f116563468134c05f94f5d7a424","datavalue":{"value":{"amount":"+0.8062124848365784","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":"Q2384400$A5C1BC6D-903F-4C05-AD77-C65B78B11710","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An extremal problem on non-full colorable graphs","badges":[]}}}}}