{"entities":{"Q6973980":{"pageid":21346935,"ns":120,"title":"Item:Q6973980","lastrevid":101367761,"modified":"2026-06-06T00:59:31Z","type":"item","id":"Q6973980","labels":{"en":{"language":"en","value":"\\(\\mathcal{O}(VE)\\) time algorithms for the Grundy (first-fit) chromatic number of block graphs and graphs with large girth"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8050510"}},"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":"Q6973980$7B4F9CAE-DE96-474D-93D6-0B2D39B9E872","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"143c08b05ed36006a8648730d60e04d970641f42","datavalue":{"value":{"text":"\\(\\mathcal{O}(VE)\\) time algorithms for the Grundy (first-fit) chromatic number of block graphs and graphs with large girth","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6973980$42924962-38BF-43E7-AD71-1C7AB1D0EA6C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"35ba2fe8c64adf7d3ebe8c0d0f9672e16631f3a9","datavalue":{"value":"1568.05083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6973980$04C588CD-A2B3-4705-A4C9-AD878BD9E575","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dc36edd2cc96abfea5bde40d45f80a8bcfb15c80","datavalue":{"value":"10.1016/J.DISC.2025.114502","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6973980$27C01816-AF8C-4592-ACB5-5266EC74C764","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b66e7e7433a273d8b90445b97e8b5a6dcb77bb5","datavalue":{"value":{"entity-type":"item","numeric-id":260060,"id":"Q260060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$483729DC-8153-4D11-AD27-4291B79F2472","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$B53AE415-AF91-4BBB-857B-EF2FB0D68B74","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f6b9aa32cd4bfe489f35b7aca3fda977d4e5555c","datavalue":{"value":{"time":"+2025-06-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6973980$7B3DF8B5-EE20-4A50-A1B9-466E9DC2FF32","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6a9684b25bfae2d0abe2a3d0781cba517fd615c4","datavalue":{"value":"The Grundy (or First-Fit) chromatic number of a graph \\(G = (V , E)\\), denoted by \\(\\Gamma(G)\\), is the maximum number of colors used by a First-Fit (greedy) coloring of \\(G\\). The determining \\(\\Gamma(G)\\) is NP-complete for various classes of graphs. Also, there exists a constant \\(c > 0\\) such that the Grundy number is hard to approximate within the ratio \\(c\\). In this paper, the author obtains an \\(\\mathcal{O}(V E)\\) algorithm to determine the Grundy number of block graphs, i.e. graphs in which every biconnected component is a complete graph and proves that the Grundy number of a general graph \\(G\\) with cut-vertices is upper bounded by the Grundy number of a block graph corresponding to \\(G\\). This provides a reasonable upper bound for the Grundy number of graphs with cut-vertices. It is proposed an \\(\\mathcal{O}(V E)\\) algorithm to determine \\(\\Gamma(G)\\) for graphs \\(G\\) whose girth \\(g\\) is at least \\(2\\Delta_{2}(G) + 1\\), where \\(\\Delta_{2}(G) = \\max_{u\\in V} \\max_{v\\in N(u):d(v)\\leq d(u)}d(v)\\). This algorithm provides a polynomial time approximation algorithm within ratio \\(\\min\\{1, (g +1)/(2\\Delta_{2}(G)+2)\\}\\) for \\(\\Gamma(G)\\) of general graphs \\(G\\) with girth \\(g\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q6973980$0D8FD6A5-C5B7-4773-AE38-877180124A1F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$A73D0068-0413-406A-B7D2-C61735ABEE4C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6973980$AD22654F-82E5-413E-BFAF-CF90A02B0132","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6973980$2E48B4F1-2145-4379-9A03-BA51970C9D98","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"24c8687e550855ca695f9052f12f1a99395606d5","datavalue":{"value":"8050510","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6973980$8FA540D6-9324-49E5-A0D2-4685D570F55A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q6973980$152073C3-90CD-4343-B6F4-2774FF1E0A32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b9ea6745c304d2a1eba8f4d87d114f6c0d1e3b3a","datavalue":{"value":"Grundy number","type":"string"},"datatype":"string"},"type":"statement","id":"Q6973980$6D39174B-F6E4-403B-9C30-437A70B82CB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80cb480fd59517e6ba192a0b670dd0225c01ce24","datavalue":{"value":"first-fit coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q6973980$A8DD431E-6CC3-44E0-9E5A-4C63D457FD4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd16e32548a7088f777df5248fcaea221fee7c4d","datavalue":{"value":"block graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q6973980$FF9782F9-C90A-40CA-981E-D9A0BEC156EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a173748f93e4f70aa784451677e2ec88ea88e5","datavalue":{"value":"girth","type":"string"},"datatype":"string"},"type":"statement","id":"Q6973980$C563FE5F-FC16-4C66-A1A4-6DAFCA4AF1C0","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":"Q6973980$FF878E3F-F7C9-494D-A95A-19AB51CC0403","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"34b84814e059ff04cc4f54a51111c5a1cda1d69a","datavalue":{"value":{"entity-type":"item","numeric-id":2223701,"id":"Q2223701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$B3B234AA-5736-4121-B3A2-4F3E97825330","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2774f583d1f8dec3b9e5129ab31b3f3ca278d07","datavalue":{"value":{"entity-type":"item","numeric-id":6827739,"id":"Q6827739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$28204615-062A-4600-AFB3-0BBA8B8248D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c6a1f7a7bc4cd6258baebce27ca99982e99d959","datavalue":{"value":{"entity-type":"item","numeric-id":427876,"id":"Q427876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$D5B43457-F674-48EB-BD94-FBD850EF1FAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69f4a2a25a9420db16b339f53ca8ed8f8bb8ecdc","datavalue":{"value":{"entity-type":"item","numeric-id":968185,"id":"Q968185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$E250EC37-0613-44DE-825C-66AD585C4410","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24a4956304e6bb9a4c12cb7f429c7804fdc6f8de","datavalue":{"value":{"entity-type":"item","numeric-id":1136777,"id":"Q1136777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$A12AC94E-22E3-4FDD-9113-0D03F7065161","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9194e9b150f8488fef979658da21ddd0e60751fc","datavalue":{"value":{"entity-type":"item","numeric-id":3651735,"id":"Q3651735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$A926356A-36B4-4AE0-A87B-708B65473AF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"897c3f494356d80d8f8e91a321986face34c3192","datavalue":{"value":{"entity-type":"item","numeric-id":3528161,"id":"Q3528161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$44ED50DD-A1ED-4521-92E2-193346FE2B9F","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":"Q6973980$6C5DACD7-9487-4354-95D0-0F5DC05F87B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45c268eb1d128b9d49c98f3c91c8aca317739396","datavalue":{"value":{"entity-type":"item","numeric-id":1949739,"id":"Q1949739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$FF94F5A0-C3CB-4450-9610-15C4B091D7AD","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":"Q6973980$4920D0A7-160D-4B03-9491-75C0DE23DB49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"edb7b561f1201f01bb82eb2720cb233014d13e27","datavalue":{"value":{"entity-type":"item","numeric-id":1312187,"id":"Q1312187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$6A535D74-9F9A-4B0D-9EB7-0425942D2DE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fbdacdd1e23abe30f09f96625e4ad080f54f172","datavalue":{"value":{"entity-type":"item","numeric-id":4863971,"id":"Q4863971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$6BFBC65B-BBC8-462F-BFE6-2814E9FDA70F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"edddef2f224ac136162b1f065420ca11f69ec00b","datavalue":{"value":{"entity-type":"item","numeric-id":4010310,"id":"Q4010310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$E1A31051-FF18-49AD-B156-61363414DC81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4364a1b6d5927f3ab73739216329ec29c38aac99","datavalue":{"value":{"entity-type":"item","numeric-id":5387684,"id":"Q5387684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$10A586F4-FDD4-4464-A8A0-B1F78ECCACA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b521abce1989c5caaa454e759c83d35753a4b79a","datavalue":{"value":{"entity-type":"item","numeric-id":511707,"id":"Q511707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$912BE837-DB19-42B8-AF86-3C19D4ABF984","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":"Q6973980$0320C52F-1C27-4C5A-8B23-93337DD9DB84","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":"Q6973980$1A3D7078-8B0F-4E39-B5CD-DF241ED39E5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b24ffb5cd3b1dba5cec18b0c1e2d9f3361c64f9a","datavalue":{"value":{"entity-type":"item","numeric-id":2462396,"id":"Q2462396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$DE9EC2E6-80E4-4093-8FEF-14FB7FE77CD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbcfef64f6549e11eac663d7cd59eda251f32cdc","datavalue":{"value":{"entity-type":"item","numeric-id":3506313,"id":"Q3506313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$3155B473-7472-45FD-BCB1-3F19D68703E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16492ea78847dd35bca7226338c84b1635814ca1","datavalue":{"value":{"entity-type":"item","numeric-id":6657261,"id":"Q6657261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$D9724DEA-E4A6-40BB-92E8-F17A000D0290","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3261e9eaeb886beb8138a8009ee190341ce71f17","datavalue":{"value":{"entity-type":"item","numeric-id":326475,"id":"Q326475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6973980$DE5F8C75-204F-432F-8D64-043E27CCE099","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":"Q6973980$7CC2265A-9605-42AB-A62B-78E2659240DA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6973980","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6973980"}}}}}