{"entities":{"Q1759824":{"pageid":1770566,"ns":120,"title":"Item:Q1759824","lastrevid":70841169,"modified":"2026-04-13T17:37:24Z","type":"item","id":"Q1759824","labels":{"en":{"language":"en","value":"On the Grundy number of graphs with few \\(P_4\\)'s"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6109900"}},"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":"Q1759824$F96B06B4-8D91-4C76-B965-3C7D907FE9AB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7a9601e0ef32e651ce4200eac4077b163fcf9326","datavalue":{"value":{"text":"On the Grundy number of graphs with few \\(P_4\\)'s","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1759824$181E3069-4C1C-42EC-AB44-6542E5061B08","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6364fcf2af23ea385ab2dfd6677cf638d7bd5ee1","datavalue":{"value":"1296.05065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759824$3D69BC34-68CD-4BAC-B59F-1F2889FC77E2","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":"Q1759824$55F1E5DD-1D7B-47C0-BF57-89F496588456","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2f3aa46d2f66375aad8f9f235cf6aa2da570e73e","datavalue":{"value":{"time":"+2012-11-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1759824$96126BA1-5990-46DA-A47F-7C97E17AE131","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d053be071ca80b9cb6d8c937da4e1b584fafe02f","datavalue":{"value":"The paper deals with the Grundy number, that is, the largest number of colours used by any execution of the greedy algorithm to colour a graph \\(G\\). It is known that the problem of determining the Grundy number of \\(G\\) is polynomial if \\(G\\) is a \\(P_4\\)@-free graph and NP@-hard if \\(G\\) is a \\(P_5\\)-free graph.  The authors define the class of fat-extended \\(P_4\\)@-laden graphs as a modification of already introduced extended \\(P_4\\)@-laden graphs. They design a polynomial-time algorithm to determine the Grundy number of any graph in this class. Since this new class intersects the class of \\(P_5\\)-free graphs and strictly contains the class of \\(P_4\\)-free graphs, this implies that the Grundy number can be computed in polynomial time for any graph in a few classes closely related to the studied class.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759824$90EE1BA3-79FE-4F96-A3E1-00C22D3E7C36","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759824$D00EAD4A-D790-4A00-BE1A-E1D2A07E5B89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759824$A1F9CF08-3945-4E96-A68C-071EEA403529","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e23f4e58b11f108362730687e674db1be6c973d7","datavalue":{"value":"6109900","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759824$D7562353-763B-4B49-B3A7-AA388B4C5835","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b9ea6745c304d2a1eba8f4d87d114f6c0d1e3b3a","datavalue":{"value":"Grundy number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759824$5A42A0A1-3AB2-4B48-9221-564E14802942","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6a55a5b200b49117817bfe4800645dd19a4185a","datavalue":{"value":"\\(P_4\\)-classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759824$1E5CE23E-2D61-4A29-A415-D7B3F2AE1D95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1adb1579ecb6bb9aaca40d9ceb17f3584d731fa","datavalue":{"value":"modular decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759824$C2AB6141-70BA-4EC8-BD00-B411C968D022","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3afba7682709060ffe1c0bfcf0edc8ba289bfa82","datavalue":{"value":{"entity-type":"item","numeric-id":484319,"id":"Q484319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759824$B8FE7861-4B8C-45F0-A186-DE6A04CFD669","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"74e45c3f99221d7833194d9c586d4b22f068b569","datavalue":{"value":{"entity-type":"item","numeric-id":189439,"id":"Q189439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759824$54A91C16-D275-4001-9308-63C05D40111E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af45ac16b5c3b4cb5ad35340a1e807846a86d0e0","datavalue":{"value":{"entity-type":"item","numeric-id":593274,"id":"Q593274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759824$243187D1-7AF6-4EB2-B5C4-88812956D831","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":"Q1759824$7D1E5873-E913-40BA-A559-B57C3FD18F2F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"75d71f009f48da405e8e6d993e5cad34cfdd0ce9","datavalue":{"value":"https://doi.org/10.1016/j.dam.2011.08.016","type":"string"},"datatype":"url"},"type":"statement","id":"Q1759824$1B52965C-98AF-4995-8A16-3CA86B9E9129","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"309ede1a3b21507dea5c32b41c6391c777a479e4","datavalue":{"value":"W2014098222","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759824$50554C24-ED90-4F2E-B778-B136D5D8F6C5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff9d52868be71e302f41a020cd3dde1ae69f41aa","datavalue":{"value":{"entity-type":"item","numeric-id":3800062,"id":"Q3800062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759824$70BB104B-17B5-4BA9-86C4-D3FFDEB161EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8add4627ebed45e331231c9fcb96d24b9b77ef2d","datavalue":{"value":{"entity-type":"item","numeric-id":4193514,"id":"Q4193514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759824$967C46EB-C294-4080-8A72-9E1914A660F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d6daa57e152021c0caed2e68ecf9f710c293def","datavalue":{"value":{"entity-type":"item","numeric-id":1349998,"id":"Q1349998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759824$842C8C17-1296-4051-896A-7677C8BA2641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"904fbef47fb47aeed5d61932cfa523281bd82c37","datavalue":{"value":{"entity-type":"item","numeric-id":286971,"id":"Q286971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759824$03489B9B-8A93-48B6-9D9B-6B95C77278AB","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":"Q1759824$4835226B-B08E-418F-8CA1-29767EC2E378","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"696348a938ca32a870c87a870044beca67a8f92e","datavalue":{"value":{"entity-type":"item","numeric-id":3496352,"id":"Q3496352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759824$EC609B01-2F0D-469A-8479-1D435ED8B0EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41cc6a286064615a5226bdd0939f0f85a946c13e","datavalue":{"value":{"entity-type":"item","numeric-id":1167741,"id":"Q1167741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759824$24340F9C-B0AB-4167-834F-14BB3DDF6C3A","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":"Q1759824$ED58155A-A40E-4646-8068-F6F383DB33C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57b85cc0bbb730c5134992c9a8504cf0db1b0cf0","datavalue":{"value":{"entity-type":"item","numeric-id":4243805,"id":"Q4243805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759824$64063F6A-D54E-4679-A37D-A8EBD2F649C3","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":"Q1759824$CA33BB1B-8F81-4664-969E-A5DBD309F1C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"202b9eb5502a9e6d937cd593d23f4123081f0bbf","datavalue":{"value":{"entity-type":"item","numeric-id":3521955,"id":"Q3521955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759824$E93B0C7B-BEDD-452F-950A-25C974F3601A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"606a9799e9c2cb6c868537683690659f98912300","datavalue":{"value":{"entity-type":"item","numeric-id":4377448,"id":"Q4377448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759824$12DADB4E-77BA-4A85-801B-E19BE7366A74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"080e978fb09e812e1ca07b265b57a6c665016da7","datavalue":{"value":{"entity-type":"item","numeric-id":4659607,"id":"Q4659607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759824$4FC1CBEA-08B5-499D-A8F5-3F59F3D19512","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":"Q1759824$426EEDE8-1B6D-4CEF-9C99-47CE56420B7C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"48cd9024dd2770b891297f485f605bc33cfb942e","datavalue":{"value":"10.1016/J.DAM.2011.08.016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759824$1ADA1D27-819D-4440-8385-7BD5365CDB3A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf01217c48fa7b22a1ef6a8ef9e3e0558ea7ddb2","datavalue":{"value":{"entity-type":"item","numeric-id":2840510,"id":"Q2840510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9735944c35ff749081a918bd9f856cafdd382a48","datavalue":{"value":{"amount":"+0.9358135461807252","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":"Q1759824$458A59BB-A6C9-462E-87B0-1B85C3BBB295","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"126e6c7d45fad36081b549469a664f187cb91e1b","datavalue":{"value":{"entity-type":"item","numeric-id":2448891,"id":"Q2448891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db1637d501534e560a33c20e6341d411f65d3253","datavalue":{"value":{"amount":"+0.8741571307182312","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":"Q1759824$85FE851C-D1EA-47B6-B58A-8888B5FCFF55","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":"3784e045a1a59472eb7105883c73dde0daf6472b","datavalue":{"value":{"amount":"+0.8518030047416687","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":"Q1759824$A8702DF8-E80B-4E58-A65F-FC36E21AD1E1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the Grundy number of graphs with few \\(P 4\\)'s","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_Grundy_number_of_graphs_with_few_%5C(P_4%5C)%27s"}}}}}