{"entities":{"Q1567683":{"pageid":1578423,"ns":120,"title":"Item:Q1567683","lastrevid":72213459,"modified":"2026-04-14T03:22:48Z","type":"item","id":"Q1567683","labels":{"en":{"language":"en","value":"Achromatic number versus pseudoachromatic number: A counterexample to a conjecture of Hedetniemi"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1462336"}},"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":"Q1567683$8A8D61A2-EC3B-437F-9F45-F64A5D9C272D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ff2cd05ee899b92ff0fb44398ceb0d9cebf0792e","datavalue":{"value":{"text":"Achromatic number versus pseudoachromatic number: A counterexample to a conjecture of Hedetniemi","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1567683$5D92AE1F-7671-4306-985E-6DE760D874D7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"531da107fc2785b7e3f05524171e04376c4e8444","datavalue":{"value":"0948.05026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567683$69D49425-8BBF-46E9-AE78-54ACBA5E5973","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9342aeab73bb7add3eb3615021440da69881e9dd","datavalue":{"value":"10.1016/S0012-365X(00)00025-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567683$6F828051-78BE-4866-AD76-768B42F8FB40","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":"Q1567683$34380C7E-6B7B-4B49-A0F1-77A1BB010ADD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ce7843932412e0d5c566f14bc25dfa7a3675a659","datavalue":{"value":{"time":"+2000-06-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1567683$02F146B8-286B-4E64-A342-2F26DC5586CC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b149309e164a7c012577d3860491e2da8b0365dd","datavalue":{"value":"The achromatic number of a graph \\(G\\) is the largest number of colors in a proper vertex coloring of \\(G\\) so that each pair of distinct colors appear on the end vertices of some edge. The pseudoachromatic number is the corresponding parameter for not necessarily proper vertex colorings. Hedetniemi (\\url{http://cyclone.cs.clemson.edu/~hedet/coloring.html}) conjectured that the two parameters agree for all trees. The present author disproves this conjecture by constructing an infinite family of trees for which the pseudoachromatic number is greater than the achromatic number.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567683$8165E547-DD08-4B53-855D-85EDA1FE3398","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567683$A3043CCF-EAA6-4727-9B92-78EA0E135E07","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d333a9507d6c847c3116026795253f861cd680cf","datavalue":{"value":"1462336","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567683$DE373C0F-5E25-456B-92D3-FEE6E16B4D63","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3d3e1a81788fcc2e099898fb5818e400e2d76fb","datavalue":{"value":"conjecture of Hedetniemi","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567683$C4445911-EA1E-4053-A940-3A4D21BA8850","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd81b2942e8899c2ccc907b7e9232a24db5f5ce3","datavalue":{"value":"achromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567683$69B71155-87EF-4AF0-A317-B61C892A010A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85dfdbd7a975d6137b355769addaba184ea21dc4","datavalue":{"value":"vertex coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567683$0650F200-3BF8-4169-B253-530B145CCB37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d37911b7c58b8d51270ecde29c0f08175aef61c","datavalue":{"value":"pseudoachromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567683$7B153C75-8AA7-41EE-9E16-2197B64C1A52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c24938459dbf20196734dcf6c3a35c8a8724abee","datavalue":{"value":"trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567683$CADBFDE1-1DF7-4FF6-9DC9-C8AA1421C035","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a6e1f9ad498b53f98afc6a2f82e96c5f4554c2c2","datavalue":{"value":{"entity-type":"item","numeric-id":383737,"id":"Q383737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1567683$7A16177D-B7BE-41D6-BEAC-23EF9962D289","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"205b6d05d63e09819854956633396177079e7ebb","datavalue":{"value":{"entity-type":"item","numeric-id":591987,"id":"Q591987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1567683$F930874B-A3DD-4FC9-BC10-F4A7EC94C52A","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":"Q1567683$1A3BDD24-77F1-4893-BC82-BADD3F2DAE53","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"83277dea03edb4436f976dd124919cf8bb9aacb4","datavalue":{"value":"Q123162527","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567683$77C947DA-65CD-43FD-BF1F-6912A36DD937","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f576402aba46b977fc002504e3367adcd9769d4b","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00025-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1567683$E8122055-A18C-4327-BC63-39D158707946","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"302a6c5d08140d36aad4251748288bbee9c930ae","datavalue":{"value":"W2026543669","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567683$51EB89A8-62A2-42FC-A182-47F5E0B05FA0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3028fa26a91a0c7751842b9f77d748da6c8512fa","datavalue":{"value":{"entity-type":"item","numeric-id":4364806,"id":"Q4364806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f0a21d11dfa13cf57ae83c3913b2a0a14d2658a","datavalue":{"value":{"amount":"+0.801223635673523","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":"Q1567683$8894A204-6AE3-4EF7-96C3-FBD9525623A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ede3cb88e940d040636d3804f7d32fe5c7c1341f","datavalue":{"value":{"entity-type":"item","numeric-id":655680,"id":"Q655680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"433837bf6cd2f1f2491d4f41f4a9344879e35288","datavalue":{"value":{"amount":"+0.795557975769043","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":"Q1567683$AD1CD497-45A4-450B-A196-B0B9EDE18E42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35b3dbcb2421100520e714ef966277299fa8153c","datavalue":{"value":{"entity-type":"item","numeric-id":1586845,"id":"Q1586845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7138e61bf8aae56c31b9404bb293810faf767a7a","datavalue":{"value":{"amount":"+0.7953693866729736","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":"Q1567683$CBF241C1-E9E8-4D49-A794-7898BF216511","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1d770e67e276848ba06479b7801c1eb8eb55b1e","datavalue":{"value":{"entity-type":"item","numeric-id":2274002,"id":"Q2274002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19ea3e86252db0b115a985e68e7e5050f194ad08","datavalue":{"value":{"amount":"+0.7839016914367676","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":"Q1567683$C97BF413-2E4D-43EB-B1C8-F42FCFB887B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4d98a3d77a64f1658b06257fda175d3d8d8292f","datavalue":{"value":{"entity-type":"item","numeric-id":3216676,"id":"Q3216676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0de167d3464cd8f12b4918c45428128745b54953","datavalue":{"value":{"amount":"+0.7791944742202759","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":"Q1567683$4AE9CD65-4083-46D2-B165-A9822BCDA722","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Achromatic number versus pseudoachromatic number: A counterexample to a conjecture of Hedetniemi","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Achromatic_number_versus_pseudoachromatic_number:_A_counterexample_to_a_conjecture_of_Hedetniemi"}}}}}