{"entities":{"Q1063620":{"pageid":1074372,"ns":120,"title":"Item:Q1063620","lastrevid":48851263,"modified":"2026-01-06T00:20:10Z","type":"item","id":"Q1063620","labels":{"en":{"language":"en","value":"The chromatic number of the product of two 4-chromatic graphs is 4"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3918393"}},"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":"Q1063620$610944E8-A7E1-4371-9BE0-C72ADF9436C4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6449ba60f28e5b792287ab8c63b72e3bb8a2fea5","datavalue":{"value":{"text":"The chromatic number of the product of two 4-chromatic graphs is 4","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1063620$413CCF4A-D715-43E4-88B1-00E10FFD1829","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9869793e5c76c95e50741e0ec7f6ebeae12e1861","datavalue":{"value":"0575.05028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063620$131DB7C4-A418-4BA6-8174-F2EE64943AAA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f9a799046b83ca4a068bb8d18b26e2dae7231691","datavalue":{"value":"10.1007/BF02579374","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063620$209EFE25-9DAA-498B-8419-F783396BF007","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063620$25A78D09-F44F-4C0A-9C3D-C944631D9191","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1063620$83089C55-F5F3-4FF1-94E7-21D0BD05EDD6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fd866539c94a390f1dfb9fa58e711c3c4e8eafc6","datavalue":{"value":"The product \\(G\\times H\\) of two graphs G and H is the graph whose vertex set is \\(V(G)\\times V(H)\\) and whose edge set consists of all pairs \\(((a,b), (\\bar a,\\bar b))\\) such that \\((a,\\bar a)\\) and \\((b,\\bar b)\\) are edges of G and H respectively. The chromatic number of the product is early seen to satisfy the bound \\(\\chi(G\\times H)\\leq \\min\\{\\chi(G),\\chi(H)\\}\\). \\textit{S. Hedetniemi} [Homomorphisms of graphs and automata, Univ. of Michigan Technical report 03105-44-T (1966)] has conjectured that equality holds in this bound, verifying this when the right-hand side is 3. The present paper verifies this conjecture when the right-hand side is 4.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063620$981BD0D3-F9A0-4D09-A51A-8A4CF6600B39","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1bb67f5051a1ca05cadb77d1c50de8e8c2b9a63b","datavalue":{"value":{"entity-type":"item","numeric-id":580347,"id":"Q580347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063620$4D346A42-13EE-4665-9955-2B617BEB31A7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063620$1B33C78D-6CA9-48D0-A362-55367371E88A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"127ce82ceb5d952692ead6addcd427ed2c3f4f1f","datavalue":{"value":"3918393","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063620$45FFB8EA-7478-4485-BF35-FB10F91BBAC0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a02790eb257c562a1e1481d0e881405f53826198","datavalue":{"value":"product of graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063620$00AC04E5-FBA1-4E77-9633-F4D8EE5B2ED4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063620$2AAD2DE7-F139-4535-B9CE-4A0927FCB148","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"0eb499f8c01d978678fff0ae06deb309c22f0020","datavalue":{"value":"Q64356946","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063620$1459B422-278C-4C60-95A5-72C85940E96E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8fb051dbca1731816c197972310c32376f5b8322","datavalue":{"value":{"entity-type":"item","numeric-id":799689,"id":"Q799689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063620$C72670E0-1708-4ED9-8F11-7C16784654D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ebff99eeb8491a02d6db5829740ad7a4f4e4bd0","datavalue":{"value":{"entity-type":"item","numeric-id":532123,"id":"Q532123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063620$CDEC5763-0CBF-4594-8D64-DEFB7C96E945","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":"Q1063620$CD3C8C8E-A978-4BD3-9856-F287AE619ADD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"99b23c5616fca5ce7e6cc41d1a4fedcfd3c84f11","datavalue":{"value":{"entity-type":"item","numeric-id":3815317,"id":"Q3815317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063620$FC537BC1-B603-4F20-980D-AC9550CD047D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"af3c58c07f2181563426a3088c98e5bca066865c","datavalue":{"value":"https://doi.org/10.1007/bf02579374","type":"string"},"datatype":"url"},"type":"statement","id":"Q1063620$D64A0822-E117-486A-85CC-FA87C1564ABB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8a9185c199eddabfdae8971359982d8947777d31","datavalue":{"value":"W2095076239","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063620$9668E298-0CF2-4008-9DCE-BCCCA4192F60","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"c96680dfe6ad3204c7dcef3a2f131a13f568b32f","datavalue":{"value":"journals/combinatorica/El-ZaharS85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063620$C237758B-EA72-4AAD-9160-9930393B1FD3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6313fa1c337f65599a6f8b65e2a9b5e6f6bf8db","datavalue":{"value":{"entity-type":"item","numeric-id":4225439,"id":"Q4225439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"695e9f5af074c99c2ad6ad329bb4d6fa9a1e90d2","datavalue":{"value":{"amount":"+0.9442481994628906","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":"Q1063620$5D54824F-B84E-4935-A61F-E9EF961D23A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fe94ef9b1d0079b7e350a9eb23b2aa38e346341","datavalue":{"value":{"entity-type":"item","numeric-id":2151188,"id":"Q2151188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"695e9f5af074c99c2ad6ad329bb4d6fa9a1e90d2","datavalue":{"value":{"amount":"+0.9442481994628906","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":"Q1063620$527CE36D-E260-48F0-B647-F7301845825F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9434dc4fa1878e7ed967f3c54e0c3305049504e0","datavalue":{"value":{"entity-type":"item","numeric-id":3815317,"id":"Q3815317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc70fc8750234aa6d6c98ca445ab4ec2088a448c","datavalue":{"value":{"amount":"+0.907088041305542","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":"Q1063620$33B370A0-FAD8-4BDA-A0EB-FF3B3153042F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d38820d0de01069a1e2bc8c658cfdd17429a4517","datavalue":{"value":{"entity-type":"item","numeric-id":1387740,"id":"Q1387740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b808af901e94b3e11483cd8f507488d37f028f47","datavalue":{"value":{"amount":"+0.8636658191680908","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":"Q1063620$AC590A7C-7642-497B-A830-460419E674F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b75eefd55b1c0b0a676937d5f56797d6f57c4402","datavalue":{"value":{"entity-type":"item","numeric-id":2570106,"id":"Q2570106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b808af901e94b3e11483cd8f507488d37f028f47","datavalue":{"value":{"amount":"+0.8636658191680908","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":"Q1063620$3817A3D3-FE80-4806-988A-F028E5D0670D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1063620","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1063620"}}}}}