{"entities":{"Q6136674":{"pageid":13270981,"ns":120,"title":"Item:Q6136674","lastrevid":58710459,"modified":"2026-04-06T10:26:19Z","type":"item","id":"Q6136674","labels":{"en":{"language":"en","value":"The list-coloring function of signed graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7790184"}},"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":"Q6136674$AA3C196E-B228-4521-B4AC-63A64727FA94","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b9077c8c0b98de839ea3a11532cb04b6a391a68a","datavalue":{"value":{"text":"The list-coloring function of signed graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6136674$2B0BCAC8-0DC8-4362-B73A-DC5D6CE8010E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"abbb9f336aab46d7393fefb7691ac6e77f70ad2c","datavalue":{"value":{"entity-type":"item","numeric-id":2093099,"id":"Q2093099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6136674$8327C4CF-B33C-42B8-B15C-E61A665F1C28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"427ad81cb678607c612fd0279eec65c495fd1865","datavalue":{"value":{"entity-type":"item","numeric-id":1734960,"id":"Q1734960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6136674$D8348F5A-DC71-4370-AA1D-F8F41A0352B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a458007c758aefa268f7dd0cff1f712c12c497a0","datavalue":{"value":{"entity-type":"item","numeric-id":345102,"id":"Q345102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6136674$787C0595-5F77-4948-A90C-B9F53A1A3846","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":"Q6136674$A422AFD1-1132-4A2F-8E94-707C6E90A520","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f3706e6c6666e19fa7ecd04e85d72fb77080ad2e","datavalue":{"value":{"time":"+2024-01-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6136674$B87AB9CF-E83B-493F-B0CF-4B7517C92DAE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6e104fc28d39f6735a551b5d3906141e9d4a7707","datavalue":{"value":"https://arxiv.org/abs/2207.05262","type":"string"},"datatype":"url"},"type":"statement","id":"Q6136674$73923EC5-ED80-4870-9C36-61C003842FF7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8dadebf0e6bbe901bc38d8e097695e0ff00f2883","datavalue":{"value":"Let \\(G\\) be a graph. Together with a function \\(\\sigma:E(G)\\rightarrow\\{-1,1\\}\\) is \\(\\Sigma=(G,\\sigma)\\) a signed graph. A \\(k\\)-coloring of \\(\\Sigma\\) is a map \\(V(G)\\rightarrow\\{0,\\pm 1,\\dots,\\pm t\\}\\) such that \\(c(u)\\neq\\sigma(e)c(v)\\) for every edge \\(e=uv\\). The number of all \\(k\\)-colorings of \\(\\Sigma\\) is denoted by \\(P(\\Sigma,k)\\).  Let \\(L(v)\\) be a list of \\(\\ell\\) colors that is given for any vertex \\(v\\in V(G)\\). An \\(L\\)-coloring of \\(\\Sigma\\) is a coloring \\(c\\) such that \\(c(v)\\in L(v)\\) for every \\(v\\in V(G)\\) and \\(P(\\Sigma,L)\\) denotes the number of all \\(L\\)-colorings of \\(\\Sigma\\). Finally, the minimum number of \\(L\\)-colorings of \\(\\Sigma\\) over all possible list assignments \\(L\\) of length \\(\\ell\\) is denoted by \\(P_t(\\Sigma,\\ell)\\).  The main result of this contribution is that if \\(\\ell\\) is greater than a specific function of the number of edges, then \\(P_t(\\Sigma,\\ell)=P(\\Sigma,\\ell)\\). The same equality was proven by \\textit{A. V. Kostochka} and \\textit{A. F. Sidorenko} [Ann. Discrete Math. 51, 375--384 (1992; \\url{doi:10.1016/S0167-5060(08)70659-9})] for chordal graphs for any \\(\\ell\\). The step toward arbitrary graphs was done by \\textit{Q. Donner} [J. Graph Theory 16, No. 3, 239--245 (1992; Zbl 0754.05038)] who showed that the equality holds for large enough \\(\\ell\\). Later, \\textit{C. Thomassen} [J. Comb. Theory, Ser. B 99, No. 2, 474--479 (2009; Zbl 1197.05061)] shown that \\(\\ell>10^n\\), \\(n=|V(G)|\\), is enough for the mentioned equality to hold. Hence, the present result is the improvement of the previous effort on this topic.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6136674$E156B589-823B-48C2-B3DF-1D165CFF077D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7fbfd6a9c9db4c04ae1819627a7c5da1a84e5679","datavalue":{"value":{"entity-type":"item","numeric-id":279208,"id":"Q279208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6136674$CD3466A2-DECF-4210-BD99-8B69F7FE0388","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6136674$DCB8327D-7C85-48FA-856F-F837FED70D98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b2773d305bb22ed635d748bc939993c6750608ab","datavalue":{"value":"05C22","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6136674$078EC467-A846-4AF1-A8D4-051C0C4E36E8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b807eb71532be5d701535de0dad4661687654b41","datavalue":{"value":"7790184","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6136674$F3314CFD-E9AA-4D88-8E13-B80E00CE789A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f7c713001b6ae067de075dc4b8ffb48f907aa82","datavalue":{"value":"signed graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6136674$10D52FAE-FD1B-43CF-9D49-D6C3C4EED038","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5f6aefdf1ffec3bc08d67d0b64a04330c0d9134","datavalue":{"value":"list coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q6136674$727CB747-37F4-45ED-9FA0-FB7351528616","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8bb5a3bdd02e15d82774007e12bf5b3ff92f00c","datavalue":{"value":"number of list colorings","type":"string"},"datatype":"string"},"type":"statement","id":"Q6136674$A6BC2388-1015-42CA-9C18-D598FA7FD95D","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":"Q6136674$9ACD7438-E9FB-4476-BDE1-A46DE0CB240C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"29ba23eeb3ddc6fdbed8f61b3f0f214435f3bedf","datavalue":{"value":"W4388812527","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6136674$D4EC928C-CA04-4D58-8157-BD826180DA4B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1177abe33b9515501a2b219923405416a93a9160","datavalue":{"value":{"entity-type":"item","numeric-id":470960,"id":"Q470960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6136674$A2F79725-8DB0-48E9-B8BE-2AC14FCBB87E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29bc8d063124c1ee7c781a2e4a03cef860467a6f","datavalue":{"value":{"entity-type":"item","numeric-id":4013427,"id":"Q4013427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6136674$83A50FFB-79E4-4237-8A1C-4DAEA288BFB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3573b87026595a32002fa2dc54ac8b096bc29f3f","datavalue":{"value":{"entity-type":"item","numeric-id":3922703,"id":"Q3922703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6136674$D3D549FA-4309-4099-8CCF-3E1C89EF3203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e84c55ba2cc510ae0d2e03d95404177492c9bfb1","datavalue":{"value":{"entity-type":"item","numeric-id":907266,"id":"Q907266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6136674$FEEAA810-1602-42FB-BEE1-013AEE7A953E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83fea97cbdef947b4a4534fdcd2d6dedd9488701","datavalue":{"value":{"entity-type":"item","numeric-id":2166295,"id":"Q2166295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6136674$D063FEB6-024A-41D3-A949-8019F3282662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42373f060c9ad9171cc11aed0ee94892f3ad097c","datavalue":{"value":{"entity-type":"item","numeric-id":1003851,"id":"Q1003851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6136674$C95928D0-955E-412D-A999-D078C9586D6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95baef9ea439f84ba8445e6d58920c2302167cc9","datavalue":{"value":{"entity-type":"item","numeric-id":345104,"id":"Q345104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6136674$089416E6-443F-4038-89CF-F464D0AF58B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3802c0f15291f27ba0782f8cbb8dce27f6f70f68","datavalue":{"value":{"entity-type":"item","numeric-id":1165249,"id":"Q1165249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6136674$C2CD3CB9-489A-4321-B6A3-6A3A97136AC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94d63c9c78c92e7451a854f7d460a73fd448775a","datavalue":{"value":{"entity-type":"item","numeric-id":1160198,"id":"Q1160198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6136674$5884B562-53E0-487E-98A9-44BC16160071","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c24bda999dd5684fa89650d23f73f203e813c91b","datavalue":{"value":"10.1016/J.DISC.2023.113790","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6136674$AF108097-29D5-46F7-A519-BC9A42EEE36F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d77c7cee22c0d6ce68d685b8771d72c693d53b1e","datavalue":{"value":{"entity-type":"item","numeric-id":2394510,"id":"Q2394510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","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":"Q6136674$402C956B-3C38-4EF0-9BC8-71AB3CE33158","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c73c60c146b626c6b88a80f977f59e578e61b3e","datavalue":{"value":{"entity-type":"item","numeric-id":1252000,"id":"Q1252000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","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":"Q6136674$35A3F77F-C804-463E-8A47-786F346B932B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4317e9ec94f14b25bd0d18cb75b48cc0e9cec65","datavalue":{"value":{"entity-type":"item","numeric-id":5487486,"id":"Q5487486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","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":"Q6136674$EC788212-1707-4FD2-96DF-5466EEF28807","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"437974e325ac3d256820df63f473bd5a02e9ba3b","datavalue":{"value":{"entity-type":"item","numeric-id":2538977,"id":"Q2538977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","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":"Q6136674$7F25B0C8-8691-45BE-B1C3-9A089031F5D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5acac97eeb3ecbd80226a73a41c86700c511eaad","datavalue":{"value":{"entity-type":"item","numeric-id":1956767,"id":"Q1956767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","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":"Q6136674$726FB411-A25A-420D-BF91-805D5A9E799A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"532d7adb0bf276fb1f452ea79917c254b37c39fe","datavalue":{"value":{"entity-type":"item","numeric-id":5724838,"id":"Q5724838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","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":"Q6136674$7562A5C1-C20C-4113-8BED-E91BB341F1B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed3d9cc339cbe7bddd40f77a0f0221d9548c5332","datavalue":{"value":{"entity-type":"item","numeric-id":3249918,"id":"Q3249918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","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":"Q6136674$C8E03750-44BD-4CDE-8418-2644F1010E5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea31fea686d4938bc1468429cc1144747f2ddc85","datavalue":{"value":{"entity-type":"item","numeric-id":5558213,"id":"Q5558213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","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":"Q6136674$B1E3EA66-BA25-4E47-960F-0D0ACBAA0516","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6136674","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6136674"}}}}}