{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q6136674","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q6136674","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q6136674","kernelVersion":"v1","immutable":true,"modified":"2025-01-27T17:52:59Z","fdo:hasComponent":[{"@id":"#fulltext","componentId":"fulltext","mediaType":"application/pdf"}]},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q6136674","name":"The list-coloring function of signed graphs","headline":"The list-coloring function of signed graphs","description":"scientific article; zbMATH DE number 7790184","url":"https://portal.mardi4nfdi.de/entity/Q6136674","datePublished":"2024-01-17","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q2093099"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1734960"},{"@id":"https://portal.mardi4nfdi.de/entity/Q345102"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q175483"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1016/J.DISC.2023.113790","url":"https://doi.org/10.1016/J.DISC.2023.113790"},"sameAs":["https://doi.org/10.1016/J.DISC.2023.113790"],"comment":"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.","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q470960"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4013427"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3922703"},{"@id":"https://portal.mardi4nfdi.de/entity/Q907266"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2166295"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1003851"},{"@id":"https://portal.mardi4nfdi.de/entity/Q345104"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1165249"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1160198"}]},"provenance":{"prov:generatedAtTime":"2025-01-27T17:52:59Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}