{"entities":{"Q5937454":{"pageid":8114256,"ns":120,"title":"Item:Q5937454","lastrevid":41933894,"modified":"2025-05-16T15:20:30Z","type":"item","id":"Q5937454","labels":{"en":{"language":"en","value":"Acyclic orientations and chromatic generating functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1619290"}},"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":"Q5937454$7BA3A2A4-FC75-4F82-B271-9DDA09326612","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"99925d3e089c90d83c4fc439ec820ca7e15097a6","datavalue":{"value":{"text":"Acyclic orientations and chromatic generating functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5937454$2CF09163-5182-4054-A29B-88CAFA63BC65","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"04b764f95f0ca3968e849e70fa03269eb8f8b098","datavalue":{"value":"0979.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937454$0324808A-17F8-489D-B80E-F33BFC0F58C4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a1e18c621d9df3dec528056df2e55c2278327adc","datavalue":{"value":"10.1016/S0012-365X(00)00344-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937454$499A52B6-3A1E-42F7-BFF3-0D7D489330E2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c8e45add8e1d4a6e6daae1baacca9c01939615d","datavalue":{"value":{"entity-type":"item","numeric-id":189445,"id":"Q189445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937454$1FD8F028-B4C6-40BD-9226-5638A661BC13","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":"Q5937454$D57437A5-6CD2-4DAE-A2E2-A631163906BA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7f09bdbef578a377222c0ed9ff0b2d47d2ab3402","datavalue":{"value":{"time":"+2002-02-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":"Q5937454$DFD5EA3B-515C-4E69-80DA-A6432F371DB6","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":"Q5937454$2280ED9B-5572-4583-9793-A307BB0836AB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937454$292AD271-5DA8-424C-A25D-E192DA5C99AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937454$8B9C9BFE-3BBD-4B4D-B72B-DD1E5B4A1DEE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c80e59179f2ec2cdd1a64153ff617ee8016efe00","datavalue":{"value":"1619290","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937454$FFB23EEA-105B-460E-962A-BB59347B81FD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50940ff582f152d511fd3e73cca71bead0f1bf00","datavalue":{"value":"chromatic polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937454$689358CD-AA88-4744-81E0-98DAF11F4B64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd08082ecfb3b93b17c9a46ab514e0f78e6b2bec","datavalue":{"value":"acyclic orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937454$8E4F307C-8F0D-4F14-8A2E-677A63AD7D15","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":"Q5937454$DF7D2CF1-E76B-4D87-9FDB-0EE000F12057","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ddfc978250f15b527df58c4e17f7d0247b10cd0","datavalue":{"value":{"entity-type":"item","numeric-id":5952156,"id":"Q5952156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05b1e507cba88a1cff9fa0729b448cadbdbc8589","datavalue":{"value":{"amount":"+0.9657022","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5937454$1C979389-B35B-4418-81E7-7FEEF4A35D38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b94d3aa57ebf8d72938a68b8a10d3a5ee736d679","datavalue":{"value":{"entity-type":"item","numeric-id":3129826,"id":"Q3129826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c0a72a8a9d8ed327d03ec531da6ac6de2a241c9","datavalue":{"value":{"amount":"+0.939981","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5937454$52FD8995-7D3E-4C28-B9BD-885F15A5CD3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2596b1d9cede33edbcd1e1524f5dbfc3a928fcf5","datavalue":{"value":{"entity-type":"item","numeric-id":5918952,"id":"Q5918952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44fe220ceabb3a74e4a1e4d858f05d64f52f0e74","datavalue":{"value":{"amount":"+0.9240743","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5937454$C8CBAEE0-A3CD-42BC-837F-1CD1D0FBCF0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6d05dca3debe0729a30c3d38fb7e9bdbdbedade","datavalue":{"value":{"entity-type":"item","numeric-id":5918292,"id":"Q5918292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44fe220ceabb3a74e4a1e4d858f05d64f52f0e74","datavalue":{"value":{"amount":"+0.9240743","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5937454$8CFE7506-84D3-4207-8A10-D0A4748DA34A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28c33c13e1f17fac36d9699aac59630a6798be62","datavalue":{"value":{"entity-type":"item","numeric-id":6055397,"id":"Q6055397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f178bd8923712f2537e0a3219376bb981bdd40f0","datavalue":{"value":{"amount":"+0.9103606","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5937454$EF39EEDC-5563-4335-9CF9-D71395D51E09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6162a1cb3b1e1fd48d4f9431e6f2154be91793a3","datavalue":{"value":{"entity-type":"item","numeric-id":2563513,"id":"Q2563513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"62d397818af02ab3b3cac3e87046f5f1214293e0","datavalue":{"value":{"amount":"+0.91031027","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5937454$0792B6BC-AF96-4F00-AC35-644907322A6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1326ba58c0a05c9ef7c1f34003abcb0f9747b68","datavalue":{"value":{"entity-type":"item","numeric-id":2325756,"id":"Q2325756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7531678bceff111bc57395d753614fe6d90affb7","datavalue":{"value":{"amount":"+0.9093157","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5937454$DE2501CC-6DD9-43BE-A527-410D4C69D757","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6da47fd9182a12be3466e71ccccfd0b99312f4de","datavalue":{"value":{"entity-type":"item","numeric-id":3768909,"id":"Q3768909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ba8ab58c156eac1cf6af10b56a73b087b26d025","datavalue":{"value":{"amount":"+0.9076443","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5937454$699766D9-AB87-44D8-B57F-65A5C4DAF31E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6119f7f1495b7755e7895e751e66488f06311ac","datavalue":{"value":{"entity-type":"item","numeric-id":400508,"id":"Q400508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"037963541c8973c1ee10fdc04a46134796302698","datavalue":{"value":{"amount":"+0.9042458","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5937454$9C0AE53A-0AFF-4655-856D-8FE910F96B23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4bef5bcdc8d4461813810a20a9b217e46557c8cd","datavalue":{"value":{"entity-type":"item","numeric-id":4581287,"id":"Q4581287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"548c68d3afcb0989d3265de6e6ff395bd4defb24","datavalue":{"value":{"amount":"+0.89570594","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5937454$3B8F48CD-5F29-496C-8ECF-1751B545CBE4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"970de9ed63bffb8f10d779789622c692c95ef162","datavalue":{"value":"Let \\(P_G(k)\\) be the chromatic polynomial of a graph \\(G\\) with \\(n\\geq 2\\) vertices, none of which is isolated. Let \\(R_G(k)= P_G(k)/k(k+1)\\). Now fix two adjacent vertices \\(a\\) and \\(z\\) in \\(G\\). Let \\({\\mathcal O}\\) be an acyclic orientation of \\(G\\) having \\(a\\) as a source and \\(z\\) as a sink. A function \\(f: V(G)\\to \\{0,1,\\dots, k\\}\\) is \\({\\mathcal O}\\)-compatible if: (i) if \\((i,j)\\) is an edge of \\({\\mathcal O}\\), then \\(f(i)\\leq f(j)\\); (ii) \\(f(a)= 0\\) and \\(f(z)= k\\); (iii) if \\(s\\) is another source of \\({\\mathcal O}\\), then \\(f(s)> 0\\); and (iv) if \\(t\\) is another sink of \\({\\mathcal O}\\), then \\(f(t)< k\\). The author shows that the coefficients of the polynomial NEWLINE\\[NEWLINE(1- t)^{n- 1}\\sum^\\infty_{k= 1} R_G(k) t^kNEWLINE\\]NEWLINE are nonnegative and, in turn, that if \\(k\\) is a nonnegative integer then \\((-1)^n R_G(-k)\\) is the number of pairs \\(({\\mathcal O},f)\\) such that \\({\\mathcal O}\\) is an acyclic orientation of \\(G\\) in which \\(a\\) is a source and \\(z\\) is a sink, and \\(f\\) is an \\({\\mathcal O}\\)-compatible function from \\(V(G)\\) to \\(\\{0,1,\\dots, k\\}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937454$4205AEB2-A47A-4971-8B26-31DD161D7955","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5937454","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5937454"}}}}}