{"entities":{"Q2127607":{"pageid":2138350,"ns":120,"title":"Item:Q2127607","lastrevid":54300110,"modified":"2026-01-26T14:40:34Z","type":"item","id":"Q2127607","labels":{"en":{"language":"en","value":"On the Nash number and the diminishing Grundy number of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7510687"}},"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":"Q2127607$33995855-DD98-48DA-9130-DAC5EE78E721","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fb20daec0126320a1a8ddb23094463738669b0ce","datavalue":{"value":{"text":"On the Nash number and the diminishing Grundy number of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2127607$9F604F3E-2600-4198-B133-6F36C4B4197F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d53f3eee6664be7bc35ead9b080073fdceacb513","datavalue":{"value":"1487.05093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2127607$3BB97829-B6A0-48DE-8879-DA1A86865370","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7932d6b94992aa4c1b703833b9a933d420b1fbd0","datavalue":{"value":{"entity-type":"item","numeric-id":2127606,"id":"Q2127606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$64EC6A45-D05F-486D-B1CF-928FC27B37A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e92c0d00d1d05744a200e7aa5cbbfb7dd8f6a7ac","datavalue":{"value":{"entity-type":"item","numeric-id":2036165,"id":"Q2036165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$710E881D-4FC1-44AA-B7A3-87700C45E436","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4e8471076b9574779be9b69bcf04a02e8ebd18d","datavalue":{"value":{"entity-type":"item","numeric-id":186133,"id":"Q186133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$C6D6B1F9-9130-495F-80E8-B456170D3918","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":"Q2127607$F0F37860-D296-45A1-A214-7F16764CDBC3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c21a91fa45947d63dbf4fb3cbc276ef8f54ca614","datavalue":{"value":{"time":"+2022-04-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2127607$B404CCC6-9FCD-4F81-A803-70F2A99F8FBD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"07063466f9efc6c305c74456c274ec7012f3d6f8","datavalue":{"value":"The paper investigates properties of a graph colouring parameter introduced by \\textit{P. N. Panagopoulou} and \\textit{P. G. Spirakis} [Lect. Notes Comput. Sci. 5369, 183--195 (2008; Zbl 1183.68585)] which is inspired by game-theoretic considerations. The closely related concept of `diminishing greedy colourings' is also studied.  A Nash \\(k\\)-colouring of a graph \\(G\\) is a vertex partition into \\(k\\) sets \\(\\{S_1, \\dotsc, S_k\\}\\) such that, if \\(|S_i| \\leq |S_j|\\), then every vertex in \\(S_i\\) has a neighbour in \\(S_j\\) (this type of colouring corresponds to a `Nash equilibrium' of a certain type of games defined on graphs, and hence the name). The Nash number \\(\\operatorname{Nn}(G)\\) of a graph \\(G\\) is the maximum \\(k\\) such that \\(G\\) admits a Nash \\(k\\)-colouring.  A diminishing greedy \\(k\\)-colouring of a graph \\(G\\) is a vertex partition into \\(k\\) sets \\(\\{S_1, \\dotsc, S_k\\}\\) such that, for every \\(i < j\\), \\(|S_i| \\geq |S_j|\\) and every vertex in \\(S_j\\) has a neighbour in \\(S_i\\) (note that the difference with Nash \\(k\\)-colourings is that here for two different sets with \\(|S_i| = |S_j|\\) have no extra requirement, whereas for Nash \\(k\\)-colourings the vertices in \\(S_i\\) are required to have neighbours in \\(S_j\\) and vice versa). The diminishing Grundy number \\(\\Gamma^\\downarrow(G)\\) is the maximum \\(k\\) such that \\(G\\) has a diminishing greedy \\(k\\)-colouring.  The results of the paper can be summarised in four main types:  1.) The parameters \\(\\operatorname{Nn}(G)\\) and \\(\\Gamma^\\downarrow(G)\\) are bounded from above and below using more usual graph colouring parameters, such as the clique number, chromatic number, Grundy number, maximum degree. As an example, the bound \\(\\operatorname{Nn}(G) \\leq \\Gamma^\\downarrow(G)\\) holds, but the bound \\(\\Gamma^\\downarrow(G)\\) cannot be bounded from above by any function of \\(\\operatorname{Nn}(G)\\).  2.) Bounds in the style of \\textit{B. Reed}'s result [J. Graph Theory 27, No. 4, 177--212 (1998; Zbl 0980.05026)] that the chromatic number can be bounded from above by a non-trivial convex combination of the clique number and the maximum degree, but replacing the parameters in this formula with \\(\\operatorname{Nn}(G)\\) and \\(\\Gamma^\\downarrow(G)\\).  3.) \\(\\operatorname{Nn}(G)\\) and \\(\\Gamma^\\downarrow(G)\\) for trees and forests.  4. Complexity results for \\(\\operatorname{Nn}(G)\\) and \\(\\Gamma^\\downarrow(G)\\): both are NP-hard to compute, even when restricted to bipartite or chordal graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2127607$35D7F9A3-4401-446E-B968-A0C6E9FC5DF5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6c786c862ea96c8431b08bcbc1855c9063fc0aba","datavalue":{"value":{"entity-type":"item","numeric-id":271629,"id":"Q271629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$C3DF8F7F-7F5E-428A-9BC6-BB640C3EEC89","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2127607$B70971AD-AC0D-452D-9949-AA53C5D1038A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2127607$A6BC8B52-657B-4ECA-8762-63DA05EA80F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2127607$4E23D53D-DABA-46FC-8C38-39B7D3A431B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2127607$E4869A53-B714-404F-9BB6-4CE5401A08A6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"369b3f5d8d6bc3ff23b0d7e43aee8342a8988c73","datavalue":{"value":"7510687","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2127607$8AE2B261-91F0-49C4-BB49-F733378826F9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59e104fc9083dc8c4e491b340ba5128d82bfc9b1","datavalue":{"value":"colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2127607$6D7834FE-26C6-4F17-8393-F23FCA9B6504","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ea53aee5a3262a88a5e6db6df7827d9b83a4537","datavalue":{"value":"Grundy colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2127607$57B30108-BE9D-41AE-92CF-CBC131AF0196","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a980a7ed1c795101c6f24aa9373c1c95ff62b0ac","datavalue":{"value":"colouring parameters","type":"string"},"datatype":"string"},"type":"statement","id":"Q2127607$FDC5AD38-ECE6-41A3-BEB6-F8DAE7A40982","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8836868e1c908239a96965e3f22c08df855770f0","datavalue":{"value":"game theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q2127607$9E4D63F2-DFAE-4B39-9A6B-38AE0388F784","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2127607$1E3B7D7B-5DAB-492F-B378-98B8F0589BA6","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":"Q2127607$DB784CA7-95BC-49F7-ABFA-6EC5DE0CF234","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d6dc3185f35fb94dc2846f2003bc236dcc2c405c","datavalue":{"value":"https://doi.org/10.1016/j.dam.2022.02.025","type":"string"},"datatype":"url"},"type":"statement","id":"Q2127607$BAC66B31-746A-4000-AAC9-0EB4771D5422","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"96aadea1168a4f870116caf4e1ce2c38b9424043","datavalue":{"value":"W4220817013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2127607$50F95A58-9D0E-48FB-AC73-8B04817FFDC8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb82498cb299bba66a44a04c0436c209442b0224","datavalue":{"value":{"entity-type":"item","numeric-id":968418,"id":"Q968418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$E4AA09ED-8683-4769-910D-B1B66B1E9588","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$A3AC975F-CCAE-4BCB-9BF0-8A660DEE8807","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f769489ebcd008167a2462b44af3c2449f3ca91c","datavalue":{"value":{"entity-type":"item","numeric-id":1146685,"id":"Q1146685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$A6059F34-2D66-4951-9223-F5EB2386DC20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a6f17b0db70d30cec76dfb5c697d4e357ae140b","datavalue":{"value":{"entity-type":"item","numeric-id":1689939,"id":"Q1689939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$0306F5DD-E25E-4EA1-96BC-23DB96160B06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33ea162c969515474c05cfb43a4db128de0351fc","datavalue":{"value":{"entity-type":"item","numeric-id":3563000,"id":"Q3563000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$38A77A81-5983-4C40-993F-A23016DD895B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95f98b95de3fc63542346b5e5a52078a1b82904a","datavalue":{"value":{"entity-type":"item","numeric-id":3804717,"id":"Q3804717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$2EA5293F-4699-466C-A656-3390933C8EEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ea09820b206833407b38a9fd76fccc6253558d8","datavalue":{"value":{"entity-type":"item","numeric-id":4745272,"id":"Q4745272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$3A57F387-1EBE-4B6F-A120-349CE2EAB54B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631200adace0f14c2f6d92fc47cb2d9f5d82cdbb","datavalue":{"value":{"entity-type":"item","numeric-id":3928241,"id":"Q3928241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$6EF40E02-427B-4767-858E-0789499AC96F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"501aefe4754342fb8d5444baacca037714207964","datavalue":{"value":{"entity-type":"item","numeric-id":4999425,"id":"Q4999425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$C246EDFF-EDF7-46B5-8703-4DA8FAFEC86A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4088093b2860b13f4a495d0644dce0cb6cbf333b","datavalue":{"value":{"entity-type":"item","numeric-id":3466351,"id":"Q3466351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$1FA2C233-100B-4A46-A0D2-130D708FFA79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8dc8e3a70353874ae71b2b5e055e522ed5b6378c","datavalue":{"value":{"entity-type":"item","numeric-id":5847741,"id":"Q5847741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$DCDDA14A-696F-4DBA-8FE3-C95F86D863A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d06e569e1bb01fc68fa7e4777fb978e61432da24","datavalue":{"value":{"entity-type":"item","numeric-id":3596717,"id":"Q3596717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$061CDD85-7879-4B52-B58A-E035867CF30A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e554762d0ade9d14b4023ae4280edddd5ca15768","datavalue":{"value":{"entity-type":"item","numeric-id":4242948,"id":"Q4242948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$F980A050-2E41-48D3-A80C-E8969F822D49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bca9887cba3f09664f547111aabf08774487019b","datavalue":{"value":{"entity-type":"item","numeric-id":856867,"id":"Q856867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$63F84CDC-92C2-43BE-A23F-54D00BB30309","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b34a246508428ac62689a0f6e17e01f841a8d923","datavalue":{"value":{"entity-type":"item","numeric-id":3002782,"id":"Q3002782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2127607$77725BB3-4667-4974-9FDB-46BE5CF574F9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b32007cf9f967dea67b243ca655f1c458bc954d2","datavalue":{"value":"10.1016/J.DAM.2022.02.025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2127607$14322196-4F22-4238-9C66-01FD79C0925A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5bf620e912e9972f6e746ed9e9874ba3e8e856f","datavalue":{"value":{"entity-type":"item","numeric-id":4923951,"id":"Q4923951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16efb0785e2583cfbabb74efc1a75299d975625d","datavalue":{"value":{"amount":"+0.7890243530273438","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":"Q2127607$ECA28144-5FB7-400C-B8D6-FEA1DBBC35D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb02bdea623cee941a610bb470898b8a50da28a2","datavalue":{"value":{"entity-type":"item","numeric-id":3596717,"id":"Q3596717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09fc83b71e6f9ec4700a3bdc4be2b31c41b114d5","datavalue":{"value":{"amount":"+0.7824728488922119","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":"Q2127607$36683F14-79F9-4489-A023-A000C8E7F428","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9849316515bb5237c599f35f5ac6d93b6cb00da8","datavalue":{"value":{"entity-type":"item","numeric-id":3058701,"id":"Q3058701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16186b8326bc66529e7e9485351c59dee934e1c3","datavalue":{"value":{"amount":"+0.7617515921592712","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":"Q2127607$58F17F3C-6006-4737-A966-1C889365BF0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b63675e6eac6bd17f199e4c718e6f086ddc89217","datavalue":{"value":{"entity-type":"item","numeric-id":1956234,"id":"Q1956234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f2675d3c4b3284c08517b4df352341e741f72b2","datavalue":{"value":{"amount":"+0.7596288919448853","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":"Q2127607$DB9D081D-FFA2-4044-B7DD-6F381BDF2586","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05d2484a2a1dd28d84b578228db5dc31a7a9f57b","datavalue":{"value":{"entity-type":"item","numeric-id":1949739,"id":"Q1949739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40e26e7a31cb1074334872aef08145af763a0445","datavalue":{"value":{"amount":"+0.7366973161697388","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":"Q2127607$0E0BA2C0-CBBA-439A-993A-26EEF513F77F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2127607","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2127607"}}}}}