{"entities":{"Q456289":{"pageid":458056,"ns":120,"title":"Item:Q456289","lastrevid":77779766,"modified":"2026-05-06T10:02:22Z","type":"item","id":"Q456289","labels":{"en":{"language":"en","value":"Locally identifying coloring of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6098327"}},"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":"Q456289$849325F9-BB97-4029-83EC-C782728A3C3B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0b438f19ddb5a64de67896823e5a344f710f1dcb","datavalue":{"value":{"text":"Locally identifying coloring of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q456289$EE0A3726-BC16-4FA2-A8BC-CCBF5EDE6BAB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"66b46c6be79ceab791ae69550e2395b227e33444","datavalue":{"value":"1252.05061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456289$E08AE8E9-05BA-4F15-84E5-11F8B40316BF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a792bd8f0110eba3a97b8d810dfde0a08901327e","datavalue":{"value":{"entity-type":"item","numeric-id":252835,"id":"Q252835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456289$605C2B8F-9755-47D4-958B-1DC1C3B22515","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"692ce2048991e39aaf8d5623dc50cd220956e79b","datavalue":{"value":{"entity-type":"item","numeric-id":189438,"id":"Q189438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456289$CB648622-06A4-483C-9EDA-0BE7DE33C6B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b3826c52088f4aa88f5af749aa0df3944c777e9","datavalue":{"value":{"entity-type":"item","numeric-id":244933,"id":"Q244933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456289$8E6BFB35-4870-4EE6-B3B8-AE62DCD84316","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"70f2091b4b3633224cf8dd3ba0007696be525593","datavalue":{"value":{"entity-type":"item","numeric-id":418898,"id":"Q418898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456289$7C5122D1-A2C6-4784-A991-1980AAFBD0D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e9731cfc25047c524a2a83588667b586efc613b","datavalue":{"value":{"entity-type":"item","numeric-id":274684,"id":"Q274684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456289$5098D8AA-917C-4725-8C0F-B70886B4084C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456289$AC25B5CF-329C-4B7B-AA5B-4F83AF489EFA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6ee92d50481ed05c06549abf63f6ece88b90dd74","datavalue":{"value":{"time":"+2012-10-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q456289$F42C3B37-6890-4CC9-8BC3-327B0906DE1A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"64b2fac6503966232d6aea29aed90585b9a5b86c","datavalue":{"value":"https://arxiv.org/abs/1010.5624","type":"string"},"datatype":"url"},"type":"statement","id":"Q456289$E0DC96A6-1439-4E9D-BC89-6C1DD6C82AD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"32582a164fce5fb45440e2f11ea37d4557be0af4","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p40","type":"string"},"datatype":"url"},"type":"statement","id":"Q456289$120C29C7-70ED-4827-BE8F-2E2846739907","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b1c517f8e629a2ca6769d4116440ced98050838c","datavalue":{"value":"Summary: We introduce the notion of locally identifying coloring of a graph. A proper vertex-coloring \\(c\\) of a graph \\(G\\) is said to be locally identifying, if for any adjacent vertices \\(u\\) and \\(v\\) with distinct closed neighborhoods, the sets of colors that appear in the closed neighborhood of \\(u\\) and \\(v\\), respectively, are distinct. Let \\(\\chi_{\\text{lid}}(G)\\) be the minimum number of colors used in a locally identifying vertex-coloring of \\(G\\). In this paper, we give several bounds on \\(\\chi_{\\text{lid}}\\) for different families of graphs (planar graphs, some subclasses of perfect graphs, graphs with bounded maximum degree) and prove that deciding whether \\(\\chi_{\\text{lid}}(G)=3\\) for a subcubic bipartite graph \\(G\\) with large girth is an NP-complete problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q456289$F70C0BD7-187F-4DAB-BF81-840B586272EC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456289$71018860-DFBF-401A-916A-DACBBBB03BDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456289$9B7D5FA3-BE31-428B-A0B2-13CD4A029A7D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a5160a5f3f8ed90dba88ff2c7183134f8838a0ac","datavalue":{"value":"6098327","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456289$8039AAB7-3FCC-4B2F-8F2D-5BA2B029EB6C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59dc3f05ae5086750474dd4aad024d42f9f4c220","datavalue":{"value":"subcubic bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q456289$CAA0A6B1-A288-4164-AEB0-0EF37C147CE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"841f94229f97d3f01ed072b0551943409cb3c00d","datavalue":{"value":"identifying code","type":"string"},"datatype":"string"},"type":"statement","id":"Q456289$0F8A5005-B630-4319-BA0D-36E1C2534C83","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":"Q456289$5C53A464-7F11-4CF2-9F1E-51E8E8905F28","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"0dbc5f736cf986fa53d9a88f7d3a60e33cbe7edc","datavalue":{"value":"bafkreighrieivgl7kkocbmteizaocxwcnluhpu54qvnygz7b3imzwwqa6e","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456289$BB1F0221-B567-4460-8B90-11F97AC1CAB6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5fbdc40e93d26a6d02f8458b207970918ad56f0","datavalue":{"value":{"entity-type":"item","numeric-id":343700,"id":"Q343700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a323201e4db000ba2ba21a52bda86233be113057","datavalue":{"value":{"amount":"+0.8788579106330872","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":"Q456289$240DC3E2-30C4-4737-BDBC-7645F410C0C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ca629674c402ad1ae20fa1bb2fe668a38997154","datavalue":{"value":{"entity-type":"item","numeric-id":418899,"id":"Q418899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8814c33128430175ffc5fd87775f222ae36eb7e2","datavalue":{"value":{"amount":"+0.8769301176071167","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":"Q456289$B3818DC5-4643-494E-B908-FDD68CF68D7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"086520e2edc801ea12035ed50c8ed89407ecc5a8","datavalue":{"value":{"entity-type":"item","numeric-id":2446886,"id":"Q2446886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad1420b6bad7e18bbba752fb6fbb96e96f5e9d3a","datavalue":{"value":{"amount":"+0.8734309673309326","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":"Q456289$05AC1684-1915-492C-943A-407A74E3C6DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bc06737e8b5a3c260b2c88d299224b42e15d125","datavalue":{"value":{"entity-type":"item","numeric-id":1685965,"id":"Q1685965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7671637b22539c095ccbb8b53c7ec267ff9a3b66","datavalue":{"value":{"amount":"+0.8377466797828674","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":"Q456289$0D947075-E7F7-4BEA-9133-AA0AA1912990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18bdca0fd25ced6e027e37e644c144e4375248db","datavalue":{"value":{"entity-type":"item","numeric-id":324747,"id":"Q324747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84d704738f85fbf6bcf47367636144df135dad5e","datavalue":{"value":{"amount":"+0.8288784623146057","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":"Q456289$4B739B4B-CF43-48F3-9416-930E2D6A17B8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Locally identifying coloring of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Locally_identifying_coloring_of_graphs"}}}}}