{"entities":{"Q2380229":{"pageid":2390972,"ns":120,"title":"Item:Q2380229","lastrevid":72652299,"modified":"2026-04-14T06:19:01Z","type":"item","id":"Q2380229","labels":{"en":{"language":"en","value":"Certificates of factorisation for chromatic polynomials"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5686777"}},"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":"Q2380229$D0B4281F-54C4-4CDF-BFF5-1D7885505575","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6e2ce36373455d4593f6a8c454b8aed55b2f8640","datavalue":{"value":{"text":"Certificates of factorisation for chromatic polynomials","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2380229$70410043-15CF-49E4-95BF-2C328B31577F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"36e90ef09b2487747a2be1ff9dcd922a8ea3a63b","datavalue":{"value":"1186.05056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380229$AD60A654-E631-4105-BA96-AF4F65D3E9D7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7033e1540cad85d9c7a57e9538ddce0901452aa5","datavalue":{"value":{"entity-type":"item","numeric-id":405175,"id":"Q405175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380229$2A49F63A-D1DF-42C4-9465-2168FFA2A3BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c10b05f408b175fc9b864bccc0f940febdbc4691","datavalue":{"value":{"entity-type":"item","numeric-id":810039,"id":"Q810039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380229$8CF4FEB7-30AC-4E93-A954-13E2AD19E68C","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":"Q2380229$1C4DA891-C6FE-4109-9318-14A218F09605","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":"Q2380229$EAE55864-D40F-4392-972A-766D5C42B7F4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6298d4f14f55434c390e2aecf87c39cb2955dc9a","datavalue":{"value":"https://eudml.org/doc/227127","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380229$43E15653-4959-4964-BCF1-39D237F7F79C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"23d5b39bfc59967cee6900295b01c2f3ad4b5e8b","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r74.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380229$19235BE1-A923-49D0-8C29-0A8CD80B5912","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"daa465972aec7cf92a8a93013e4335783db1888e","datavalue":{"value":"Summary: The chromatic polynomial gives the number of proper \\(\\lambda\\)-colourings of a graph \\(G\\). This paper considers factorisation of the chromatic polynomial as a first step in an algebraic study of the roots of this polynomial. The chromatic polynomial of a graph is said to have a chromatic factorisation if \\(P(G,\\lambda)= P(H_1,\\lambda)P(H_2,\\lambda)/P(K_r,\\lambda)\\) for some graphs \\(H_1\\) and \\(H_2\\) and clique \\(K_r\\). It is known that the chromatic polynomial of any clique-separable graph, that is, a graph containing a separating \\(r\\)-clique, has a chromatic factorisation. We show that there exist other chromatic polynomials that have chromatic factorisations but are not the chromatic polynomial of any clique-separable graph and identify all such chromatic polynomials of degree at most 10. We introduce the notion of a certificate of factorisation, that is, a sequence of algebraic transformations based on identities for the chromatic polynomial that explains the factorisations for a graph. We find an upper bound of \\(n^22^{n^2/2}\\) for the lengths of these certificates, and find much smaller certificates for all chromatic factorisations of graphs of order \\(\\leq9\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380229$33AF5FD7-56F6-4044-BEEA-455358F42748","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380229$153F09D9-7CE1-4F45-84C6-329DA677CC1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380229$DBE56241-6B67-471C-86EA-E2F3DBA664B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380229$5CC7E273-2ED1-4421-B682-429C5A3D7CCB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f3a1ec0ad7b4011af2028ec513c191ba1d228a04","datavalue":{"value":"5686777","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380229$EBB1CB0C-DBE5-4EFD-98AA-E51F1771E3D9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d083cccdbcdb1e24d089fe7943900dd32ac84c4","datavalue":{"value":"chromatic polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380229$4FAA48D6-6490-43E5-81BD-0D2A8DFD5A18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5624802e7052c56ea4fbdb36d3f04c8e9bcd985","datavalue":{"value":"factorisation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380229$78E53CBB-6C0A-4480-A251-A49F70EF4727","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b5d4aa68ec3ad6c06b825a81cb25a02fb89a299f","datavalue":{"value":"chromatic factorisation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380229$487572B3-921F-42D6-AC1F-532432ECC080","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":"Q2380229$D4E2D540-0534-46E7-B444-A3CE1696A12A","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"bf132af13d776b142336f3eec6e87f7b12bc7670","datavalue":{"value":"bafkreig3d7fxkmfbyaxw22323y3j7vy5aieh7joptvy2u6uto3hfdggs2u","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380229$4AB1B10E-0F2B-43FC-BBC4-80BA95120B1D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd481d1ff6f03dfe6445ebfea4bafc362f36bce0","datavalue":{"value":{"entity-type":"item","numeric-id":2380230,"id":"Q2380230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06b9901133aaa13b1f35141737241ea39e05f261","datavalue":{"value":{"amount":"+0.933547854423523","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":"Q2380229$5ECA7C87-A282-48D9-AC46-9B7B7FBDD3E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"740485ea739381aeda6179f946eb1b1a6db78359","datavalue":{"value":{"entity-type":"item","numeric-id":409454,"id":"Q409454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1153a48f4e0e19e3e76aa39371be420723086396","datavalue":{"value":{"amount":"+0.9104647040367126","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":"Q2380229$05FFE600-226B-4AD5-9F4A-F4DE04906275","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0423b50e2826c75a5f6c5bdc4823f8bb91f627e9","datavalue":{"value":{"entity-type":"item","numeric-id":5377353,"id":"Q5377353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50488e028e35c573bd49626bb70bb2aa5e22f69c","datavalue":{"value":{"amount":"+0.8071399331092834","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":"Q2380229$7636DD6D-F98F-4A17-BD7D-CC750A5E5BEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fcfddd7b85b5a5cb9c13e63b0fe26b8003dd5a8","datavalue":{"value":{"entity-type":"item","numeric-id":405176,"id":"Q405176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe89528dfe7797f24852f19666d8228954157077","datavalue":{"value":{"amount":"+0.778986394405365","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":"Q2380229$42193F4B-73B5-4149-924D-351F33E6768E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc6e814ffa1387d30dd318a135479fae5e8a9b3a","datavalue":{"value":{"entity-type":"item","numeric-id":5298074,"id":"Q5298074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ba50b5b751832952d1d5419bf03efed9d29eb2d","datavalue":{"value":{"amount":"+0.7573304176330566","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":"Q2380229$67703B62-0389-4818-94AD-ACA3A0C43DFA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Certificates of factorisation for chromatic polynomials","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Certificates_of_factorisation_for_chromatic_polynomials"}}}}}