{"entities":{"Q2380225":{"pageid":2390968,"ns":120,"title":"Item:Q2380225","lastrevid":50939057,"modified":"2026-01-15T20:26:05Z","type":"item","id":"Q2380225","labels":{"en":{"language":"en","value":"Chromatic number for a generalization of Cartesian product graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5686774"}},"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":"Q2380225$E50D09EF-4BFF-4388-84E3-E2966DCCB610","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9cf20faef5c40071e84e7b57de56e06eb4471de2","datavalue":{"value":{"text":"Chromatic number for a generalization of Cartesian product graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2380225$3D4811FB-42A3-499F-9057-CE15A51AF835","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"eaeddbd5e69f554c363199c3fc7d2dddc91959dd","datavalue":{"value":"1186.05106","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380225$10AC0318-1264-428C-9840-BA599EF6DE5D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"53427ddbb10f2ef6b2b23d5d0945110660ad7953","datavalue":{"value":{"entity-type":"item","numeric-id":273100,"id":"Q273100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380225$9BDBBB9B-38A0-4671-B815-E69E1F7581CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4d4c73f0a1fcfa77f8c56f84fd9c0566fb0d581","datavalue":{"value":{"entity-type":"item","numeric-id":185079,"id":"Q185079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380225$5C939DF1-207D-471E-8607-05EC0F2F74F5","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":"Q2380225$E02996FA-F6D6-4A88-87DC-B25F3B1FC8D6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"143e8774a45e663375c24b3b343519cf2933b18c","datavalue":{"value":{"time":"+2010-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2380225$22A16490-4DC5-41E8-8A2B-B12F8BA4E3FB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0a7a129dc6d54b8ac8d32a7165e33feb82477c55","datavalue":{"value":"https://eudml.org/doc/223249","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380225$1A5AE1BE-9D44-4D12-BA09-79EB3B23DB3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"7e882ba27685c74495b36aecb02393fe0f31dd67","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r71.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380225$676F8600-3C3B-4F64-8451-30C358B3DAAD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6794f6b5884cd216b837e30e8cbe9ee0c89ea4c1","datavalue":{"value":"Summary: Let \\({\\mathcal G}\\) be a class of graphs. A \\(d\\)-fold grid over \\({\\mathcal G}\\) is a graph obtained from a \\(d\\)-dimensional rectangular grid of vertices by placing a graph from \\({\\mathcal G}\\) on each of the lines parallel to one of the axes. Thus each vertex belongs to d of these subgraphs. The class of \\(d\\)-fold grids over \\({\\mathcal G}\\) is denoted by \\({\\mathcal G}^d\\).  Let \\(f({\\mathcal G};d)= \\max_{G\\in{\\mathcal G}^d}(G)\\). If each graph in \\({\\mathcal G}\\) is \\(k\\)-colorable, then \\(f({\\mathcal G};d)\\leq k^d\\). We show that this bound is best possible by proving that \\(f({\\mathcal G};d)= k^d\\) when \\({\\mathcal G}\\) is the class of all \\(k\\)-colorable graphs. We also show that \\(f({\\mathcal G};d)\\geq \\left\\lfloor \\sqrt{\\frac{d}{6\\log d}}\\right\\rfloor\\) when \\({\\mathcal G}\\) is the class of graphs with at most one edge, and \\(f({\\mathcal G};d)\\geq \\lfloor \\frac{d}{6\\log d}\\rfloor\\) when \\({\\mathcal G}\\) is the class of graphs with maximum degree 1.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380225$0A476425-F965-4331-9839-D231659D8DAB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f54624d6184313158324a5b5a097f6e611a50ba5","datavalue":{"value":"05C76","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380225$CE6017CD-B22C-419A-900F-C26A4117A846","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380225$5DE28A90-2A76-4B84-BB97-E135C1189206","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"95fa7909c7a30b2fc383186e59a71f935374a943","datavalue":{"value":"5686774","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380225$83ECDD43-3023-4192-A46B-1AD3FE64383C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1d08a40f9eeb40e0e7880079fe23ffe2ada5d3c","datavalue":{"value":"d-fold grids over a graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380225$F2C124B6-261D-4261-A2D9-CA6A44ADB76E","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":"Q2380225$BB7FC556-3594-4FE8-9153-81AC1EE4F525","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"5be649e6ec10ddf3b83f358dc2c76573bb80b568","datavalue":{"value":"bafkreid37xtqufwmsdwegysotfg2kersyprt6kp7kzj342uc7xou6stmd4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380225$B2C41672-2131-4215-9F48-FC1D244CF8DF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a6ab70ef191c3591ba7e60104e0457b42849a6e","datavalue":{"value":{"entity-type":"item","numeric-id":2391545,"id":"Q2391545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b8460b5133f15db902f3c4de6963274e23cac6f","datavalue":{"value":{"amount":"+0.7836610674858093","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":"Q2380225$D74636F8-4C7F-4F41-AA00-F32A83B5F423","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"529460c8887ee8eef58c60a8599fb0d12b93a66c","datavalue":{"value":{"entity-type":"item","numeric-id":4912213,"id":"Q4912213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"998b87d74cb691c69ed0462728fa695b58f53c03","datavalue":{"value":{"amount":"+0.776364266872406","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":"Q2380225$79E201DD-6E55-4FAD-9066-937F27FE827B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"959b7058fdb645525f72c9bcb9a418dc9c8d57fb","datavalue":{"value":{"entity-type":"item","numeric-id":1706119,"id":"Q1706119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d78c75f8e798357aa3f296fe67d15795ccdd75fe","datavalue":{"value":{"amount":"+0.7758148908615112","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":"Q2380225$D1687F63-B920-40C9-AC08-71A9EAD9AF45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"837b316afa9add6e816b0292c17eb549c4b5af66","datavalue":{"value":{"entity-type":"item","numeric-id":3128559,"id":"Q3128559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eff0c7c64c9bdb4bd9a2b24b107a0fe01273f428","datavalue":{"value":{"amount":"+0.7674575448036194","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":"Q2380225$8AF5E389-2925-4E22-BEA9-F01274241C6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91587e0240a91cf0493fe59f61eafdb612aded8e","datavalue":{"value":{"entity-type":"item","numeric-id":1014392,"id":"Q1014392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf6ed4c516fbfd12c0574bf9201c884124bf725d","datavalue":{"value":{"amount":"+0.7642996907234192","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":"Q2380225$15CCEE73-2DD3-4F1E-86BB-882383526547","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2380225","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2380225"}}}}}