{"entities":{"Q1296159":{"pageid":1306909,"ns":120,"title":"Item:Q1296159","lastrevid":43009454,"modified":"2025-07-16T20:41:54Z","type":"item","id":"Q1296159","labels":{"en":{"language":"en","value":"The graph polynomial and the number of proper vertex colorings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1314960"}},"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":"Q1296159$E336368C-C696-4CF8-8385-D6E30D1BF555","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"96e946e2644fa4f25fbe1ab46031f33bafd2dac0","datavalue":{"value":{"text":"The graph polynomial and the number of proper vertex colorings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1296159$FB63A61A-B6B5-4A10-AA60-8C12689F57E6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e8de120048bc85516a4e1dc686913d23d8393739","datavalue":{"value":"0924.05027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1296159$A3F60426-D163-413C-BB55-70DD69084FBF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6528a033086d689548cd6b323306dad1d6651466","datavalue":{"value":{"entity-type":"item","numeric-id":286767,"id":"Q286767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1296159$2854DD94-AD41-4AC6-AC42-3197801D3D35","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"05439317d8a794e350c15131a8e5a6b60bc168b7","datavalue":{"value":{"time":"+1999-07-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1296159$293D486A-D1C2-4CA7-B0E0-5B37D97863DB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"23a3b59e95e121dc8e8978bbda267a356d982ee8","datavalue":{"value":"http://www.numdam.org/item?id=AIF_1999__49_3_1089_0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1296159$3043F934-304D-432B-9332-60277EABB8CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"b8da38b9365b41040512faf6a9eb776b3ca548eb","datavalue":{"value":"https://eudml.org/doc/75357","type":"string"},"datatype":"url"},"type":"statement","id":"Q1296159$E149F2A7-7A0E-4AF0-84C5-EAA2B9DCB0C2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"adf078d913f2c77b11babad3eb4df5136fbe15dd","datavalue":{"value":"The graph polynomial \\(P_G\\) of a graph \\(G=(V,E)\\), where \\(V= \\{1, \\dots, n\\}\\), is defined as  \\[ \\prod_{ij\\in E,i<j}(x_j-x_i), \\]  and \\(\\| \\overline P_G^k\\|^2_2\\) is defined as the number obtained by taking the remainder of \\(P_G\\) modulo the ideal generated by the polynomials \\(x^k_i-1\\), \\(1 \\leq i\\leq n\\), and then summing the squares of the coefficients. A formula for \\(\\| \\overline P^k_G \\|^2_2\\) in terms of proper \\(k\\)-colourings of \\(G\\) was presented in [\\textit{N. Alon} and \\textit{M. Tarsi}, A note on graph colorings and graph polynomials, J. Comb. Theory, Ser. B 70, No. 1, 197-201, Art. No. TB971753 (1991; Zbl 0883.05050)]. The article under review presents another formula for \\(\\| \\overline P^k_G \\|^2_2\\) in terms of partial edge-orientations of \\(G\\), and then compares the two formulae for \\(k=3\\) to prove that the number of proper 3-colourings of a graph \\(G\\) is congruent modulo 4 to the number of total edge-orientations of \\(G\\) in which every vertex has the same in-degree as out-degree. A consequence of this latter result is that the number of proper 3-colourings of a 4-regular graph \\(G\\) has the same parity as the number of Eulerian orientations of \\(G\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1296159$AD3F1C66-53B3-41D8-BA0F-66FFA7D5CC36","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1296159$36879EC0-C8E4-499A-A341-79AE575D7B18","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d05900fa1f4bf9a0f354831937f53740b812324e","datavalue":{"value":"1314960","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1296159$7DD24218-E0B9-4B17-8B91-B6A314541D1D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"510bd106a0c2b11b203e1b700c18caa8e1e53098","datavalue":{"value":"proper vertex colorings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1296159$3EB6977A-6D60-4E17-8BC5-745B50E18E59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4c58746c65b498a296790abd170bc3398210afd","datavalue":{"value":"graph polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q1296159$9EEC41BF-8CF9-4E3D-B638-5A58832F6A3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"60452cd9b9e035efba9fb77a15c4695edf760bbb","datavalue":{"value":"edge-orientations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1296159$5733279D-DABC-41AD-8E80-F46E9A0DC136","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f403cdd51a160f6360810d9c7ecfdb465f376016","datavalue":{"value":"Eulerian orientations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1296159$91E94F6F-011B-48C3-BEFC-95BEAEB49D67","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"457b59512685cc959c2dfec1eb05d289a709afaf","datavalue":{"value":{"entity-type":"item","numeric-id":442385,"id":"Q442385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1296159$55119E6C-4F55-44E6-8C7A-BA4CE01AE7BE","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":"Q1296159$E9A9AAB1-0581-4F4E-98F5-F6185E9628C6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f61f30c8943c373f0c7713ef5800335138b2a301","datavalue":{"value":"W1965019888","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1296159$A21D20DC-B7AC-422E-A911-8A853A56A355","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdd0676f008d3d35603ace258b7c421e863d9a84","datavalue":{"value":{"entity-type":"item","numeric-id":1196681,"id":"Q1196681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1296159$56009FFD-ADB8-4C2E-8210-0166D34C9C7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27127c49519e044568f27bedaec5e0ba161cc236","datavalue":{"value":{"entity-type":"item","numeric-id":1369660,"id":"Q1369660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1296159$63A200CC-B048-4FC0-A5FA-2993CB0BA08F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82cdc5d6f169ea67b72179b6bdff39f814ef814e","datavalue":{"value":{"entity-type":"item","numeric-id":1197012,"id":"Q1197012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1296159$F949E257-26AD-45EE-9BC3-AF540C284602","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cc492deac5bc4a2108bef824ac5c2ed1a0e841a","datavalue":{"value":{"entity-type":"item","numeric-id":4284625,"id":"Q4284625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1296159$DE21A1D1-A9C7-4FC3-8DE7-513CF83E00FD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"363b3c618e1874602d16b7e7321ca65df5dd7144","datavalue":{"value":"10.5802/AIF.1707","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1296159$821AE80D-5411-4768-ABC2-06426621A58B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96ce369c9c25f33a72a16233515a7ef4a34135ea","datavalue":{"value":{"entity-type":"item","numeric-id":1176747,"id":"Q1176747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44a99baeaee640c561507451548cde1d85307f3b","datavalue":{"value":{"amount":"+0.7382989","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":"Q1296159$05D4750D-9B52-4DAA-9116-37D70A14C406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"854a8207ab2626ff70283b376234a710558ea880","datavalue":{"value":{"entity-type":"item","numeric-id":1902912,"id":"Q1902912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f225d9b67845f636c8b8a15bff7972e9395eb3d7","datavalue":{"value":{"amount":"+0.73024607","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":"Q1296159$7FE2E982-37F7-4FF5-8D43-6715A11B9C83","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":"24045c01ae4adb30c445c81a217715e2a4f18b1f","datavalue":{"value":{"amount":"+0.72746813","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":"Q1296159$4BA06C00-633B-4C5A-9192-2A00C26C0B07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"254aa28fd6eb8c59c6718362beb731ff59d0cc50","datavalue":{"value":{"entity-type":"item","numeric-id":3092687,"id":"Q3092687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"932c77bc38da83b8fa296d2a861c96be10c1ca68","datavalue":{"value":{"amount":"+0.72647834","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":"Q1296159$8DDB4334-FAA6-4D08-8AEB-D5D8BE9CDF6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f67b4966cd34a682ebf7bbb8baf01ee71b74e895","datavalue":{"value":{"entity-type":"item","numeric-id":1781373,"id":"Q1781373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb646bce44b043f98283beb45ea5998d6afd6413","datavalue":{"value":{"amount":"+0.7214505","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":"Q1296159$E656C053-C44B-4155-B4D6-8520E1B81418","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0b49a88d91828d22bc0399eea2dc1eca77fb6f6","datavalue":{"value":{"entity-type":"item","numeric-id":491743,"id":"Q491743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"640fb62421faf13a0bd764e867e9c95171d4d741","datavalue":{"value":{"amount":"+0.7166512","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":"Q1296159$4B97D1F7-3A63-48F5-A598-9F0CBB5EBF71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fed3b53aeeaff65f3194c6d0478b30fcad6f5838","datavalue":{"value":{"entity-type":"item","numeric-id":1644957,"id":"Q1644957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6113be96cf6e3b15f9247671cebdddadb395e41","datavalue":{"value":{"amount":"+0.716474","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":"Q1296159$6D729CD3-E813-41B6-A4C8-846508D2A5F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aba5a05aa8db12da9812610c0d1fa67d0701e27e","datavalue":{"value":{"entity-type":"item","numeric-id":1343771,"id":"Q1343771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"155ec3b258b16911c8e7e28abbaeab496416e962","datavalue":{"value":{"amount":"+0.7148191","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":"Q1296159$4471B48F-2F0D-49E8-B174-86489F0BC830","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e5368eae45fc92aa25c3874b469192a74fa0ab5","datavalue":{"value":{"entity-type":"item","numeric-id":4314371,"id":"Q4314371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ee6e4c2341a34c8df13284def8819a3ae25564d","datavalue":{"value":{"amount":"+0.7140154","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":"Q1296159$3E523D1E-FB47-4B17-8701-791714FA997F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57f903d71045d9125fa25bcefece72db1daf0bf1","datavalue":{"value":{"entity-type":"item","numeric-id":6169806,"id":"Q6169806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74d9693409a5ed82936627aa3f6c2aec937c7d30","datavalue":{"value":{"amount":"+0.7133821","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":"Q1296159$F3E0D068-48F2-4084-914B-F74ACB94ED01","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"dc1a1beeefbfbbcf5aa3adaae27b74e0e5ad168d","datavalue":{"value":{"entity-type":"item","numeric-id":4557581,"id":"Q4557581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1296159$A8EA1484-277D-496A-A2F4-05FB0FCDD565","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1296159","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1296159"}}}}}