{"entities":{"Q1059638":{"pageid":1061486,"ns":120,"title":"Item:Q1059638","lastrevid":66652176,"modified":"2026-04-12T11:34:11Z","type":"item","id":"Q1059638","labels":{"en":{"language":"en","value":"The chromatic polynomial of an unlabeled graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3904613"}},"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":"Q1059638$CB8951DE-2EC6-4583-9F0D-7D4AC3A7F7FE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6fe9de0dde3671900e3739776ee228859117465e","datavalue":{"value":{"text":"The chromatic polynomial of an unlabeled graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1059638$C5B57972-158F-4052-86AC-C394DC4D7AAC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ba2d3fc25fd39cd459edae3058fd667dda3654dd","datavalue":{"value":"0567.05025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059638$DDD05C91-ED69-4023-BC13-7507BF7A3872","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dc4d62e5c153757bb0ef63f12bf027f209273815","datavalue":{"value":"10.1016/0095-8956(85)90068-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059638$086417A2-AEC4-40D4-A3BE-68A4295789D8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059638$1CD32B57-C166-4F34-87B8-8EABDE87AE9E","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":"Q1059638$DF4566B0-E2FD-48EC-B1C8-70FAE228EAB3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3b353ba8bce5fb51927687d0b21ed303e4e3e696","datavalue":{"value":"We investigate the chromatic polynomial \\(\\chi\\) (G,\\(\\lambda)\\) of an unlabeled graph G. It is shown that \\(\\chi (G,\\lambda)=(1/| A(g)|)\\sum_{\\pi \\in A(g)}\\chi (g,\\pi,\\lambda),\\) where g is any labeled version of G, A(g) is the automorphism group of g and \\(\\chi\\) (g,\\(\\pi\\),\\(\\lambda)\\) is the chromatic polynomial for colorings of g fixed by \\(\\pi\\). The above expression shows that \\(\\chi\\) (G,\\(\\lambda)\\) is a rational polynomial of degree \\(n=| V(G)|\\) with leading coefficient 1/\\(| A(g)|\\). Though \\(\\chi\\) (G,\\(\\lambda)\\) does not satisfy chromatic reduction, each polynomial \\(\\chi\\) (g,\\(\\pi\\),\\(\\lambda)\\) does, thus yielding a simple method for computing \\(\\chi\\) (G,\\(\\lambda)\\). We also show that the number N(G) of acyclic orientations of G is related to the argument \\(\\lambda =-1\\) by the formula \\(N(G)=(1/| A(g)|)\\sum_{\\pi \\in A(g)}(-1)^{s(\\pi)}\\chi (g,\\pi,-1),\\) where s(\\(\\pi)\\) is the number of cycles of \\(\\pi\\). This information is used to derive Robinson's cycle index sum equations for counting unlabeled acyclic digraphs [cf. \\textit{R. W. Robinson}, Comb. Math. V, Proc. 5th Aust. Conf., Melbourne 1976, Lect. Notes Math. 622, 28-43 (1977; Zbl 0376.05031)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1059638$A9F37A89-3AA8-4D8C-8EC7-59590882DD5C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059638$BDA4391D-3506-4760-ACC8-C25EEA551971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059638$AA3AFA93-4EFF-4A7A-94F8-552FA387A2F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059638$B918953D-3A33-4AA4-AE44-15F26CC47ED7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"faeef258a1c84a70c4bfa5ee0daa0a7ad4332ea9","datavalue":{"value":"3904613","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059638$EAB49F6D-8495-440E-B543-D01DB612BBB5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50940ff582f152d511fd3e73cca71bead0f1bf00","datavalue":{"value":"chromatic polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q1059638$A05218C8-49FC-458C-ABB1-BEE57A0FED18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"14890318cff84c4eab8b7ba7c3f979e09c773376","datavalue":{"value":"unlabeled graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1059638$A1993D1D-14CF-4298-8A67-8E4ECC0B4651","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eeef367fa1da059c9143ea57ff92f9bf126feee9","datavalue":{"value":"acyclic orientations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1059638$BD786F00-F3C3-41C7-B6FA-0C3EE95539DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21a5664c92f23413aa9bd56f8ce0b04bf32c806e","datavalue":{"value":"cycle index sum equations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1059638$142D0C3F-1EFF-44A3-AAF8-DA3CDE727984","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36fab40ffbf97effbc0e6e85109aea021b4ab833","datavalue":{"value":"counting unlabeled acyclic digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1059638$9BCBC056-DA33-41EC-9939-E5C950DD1D67","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6ab369a5ae33f7863f98b4f260adf8fc0b70482b","datavalue":{"value":{"entity-type":"item","numeric-id":222789,"id":"Q222789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059638$C19E366F-F0E3-4C08-B543-A4CA7F85E911","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9e2ce415b05e6670b991fe9e65a3d9420c1fa95d","datavalue":{"value":{"entity-type":"item","numeric-id":754227,"id":"Q754227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059638$A0CBA169-8407-4F43-814B-F8EEF57DAD76","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":"Q1059638$863B8F6C-EBAD-472C-AA83-A8F56E18F251","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"db9f60956eb3285eb30d71622f93e7e352ee7b1c","datavalue":{"value":"https://doi.org/10.1016/0095-8956(85)90068-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1059638$2EE4A1A7-0D28-476E-AEAF-F2C8C3E11B9F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ba6bce72a561241af4482bcf2d229885ce81b9bb","datavalue":{"value":"W2086575992","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059638$CB802F30-3DEB-455A-8B24-B3CBC46F9083","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cff90b53746deaf40f0bd975035788d645dc76ab","datavalue":{"value":{"entity-type":"item","numeric-id":5682013,"id":"Q5682013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059638$E0F04350-3B8B-4249-BF84-7A8EF4907B61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebd7155c3b1b6a4d7c5be5cec5fc2a097326d7f0","datavalue":{"value":{"entity-type":"item","numeric-id":4154580,"id":"Q4154580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059638$3679C70E-6A8F-4B1A-81BA-783E6E49D382","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2aa74053b99e4e74b3e4ed9742e7abbebc0d543d","datavalue":{"value":{"entity-type":"item","numeric-id":2559389,"id":"Q2559389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059638$75780CFF-BE51-439B-B63C-438CE6C4EFE4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63180dde02b4d66f9a3f76b0f3acf83e411c8ba8","datavalue":{"value":{"entity-type":"item","numeric-id":4697566,"id":"Q4697566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d41cc848872f1479f04b2165eb5b6d6a0d906aa6","datavalue":{"value":{"amount":"+0.8371521","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059638$7AA49C3D-1515-4EDB-B0F9-4B5136590D54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5996017e333171bc7410a7d574b1d7c01f9aeb43","datavalue":{"value":{"entity-type":"item","numeric-id":3470477,"id":"Q3470477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f69f5de32f21ba1167b1b6e113ae48f9659a300","datavalue":{"value":{"amount":"+0.7776078","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059638$B0DBDBBE-EA0F-47D4-8DCB-8F5D35717F9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"466457e6b84ea5893764bc29db2ba47c2e9ff367","datavalue":{"value":{"entity-type":"item","numeric-id":2323915,"id":"Q2323915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b81ccc539429f80dbb51066e0f7fd3f9905d17d","datavalue":{"value":{"amount":"+0.7580713","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059638$2EDBECC5-2061-4BF3-8BFD-49C2797BA313","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93ab1ef73fcc4d8e3a41b05a12d263e58c9aecdc","datavalue":{"value":{"entity-type":"item","numeric-id":804584,"id":"Q804584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a336e3288caf566231841172141ff3f26bffea47","datavalue":{"value":{"amount":"+0.71681184","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059638$5FE8C7CC-1D27-4CEF-BF10-3ACF3ACFD867","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d445cb91dcbc4111dafd57ef40eb6cb68a84d34","datavalue":{"value":{"entity-type":"item","numeric-id":5443197,"id":"Q5443197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c22115817fe9db065046495bdb6bfbe4f76148a","datavalue":{"value":{"amount":"+0.7162312","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059638$849353CD-B2F9-4678-8205-DE2DDA8F2BD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8516333824ccf0184318b6e9754f3be8ac74095","datavalue":{"value":{"entity-type":"item","numeric-id":801080,"id":"Q801080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffd48cb72e88ac0c582c7d5af9669ebf8a163096","datavalue":{"value":{"amount":"+0.7148849","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059638$79193FFE-A500-41EF-A6E0-7347F2DFB756","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10eed8222a858a0629917fc792687ff9a809d456","datavalue":{"value":{"entity-type":"item","numeric-id":2497989,"id":"Q2497989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"665a7ef887e90232f7263a4fc234eb1243ac7d06","datavalue":{"value":{"amount":"+0.712843","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059638$2F02FF3D-C138-4339-9454-B97E26269AE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4957e9dc0271c0d3552daeac8c5a88fa6b1cc155","datavalue":{"value":{"entity-type":"item","numeric-id":2841548,"id":"Q2841548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0abc753600374802764b9deddeebe655d2a1ee3","datavalue":{"value":{"amount":"+0.7121249","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059638$1E434D7B-EC6D-4922-9392-C6CD701C2433","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1c2cbe4e183010abcdc0bfed20f7f370631c058","datavalue":{"value":{"entity-type":"item","numeric-id":3720619,"id":"Q3720619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71b4aba692bb9593c0164370338ff7ab38cae325","datavalue":{"value":{"amount":"+0.7116841","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059638$3BE18454-1C1B-4998-8392-B19061679BA2","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":"557f89bb27d3c679fe624dc554bdbdc195427da9","datavalue":{"value":{"amount":"+0.71106225","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059638$FE5ECA01-03F5-47BD-B2E1-B64289210F53","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The chromatic polynomial of an unlabeled graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_chromatic_polynomial_of_an_unlabeled_graph"}}}}}