The list-coloring function of signed graphs

DOI10.1016/J.DISC.2023.113790MaRDI QIDQ6136674zbMATH OpenOpenAlexFDO

Authors Sumin Huang, Jianguo Qian, Wei Wang

Publication date 17 January 2024

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.05262

zbMATH Keywords

list coloringnumber of list coloringssigned graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22)

Abstract: It is known that, for any $k$-list assignment $L$ of a graph $G$, the number of $L$-list colorings of $G$ is at least the number of the proper $k$-colorings of $G$ when $k>(m-1)/ln(1+sqrt2)$. In this paper, we extend the Whitney's broken cycle theorem to $L$-colorings of signed graphs, by which we show that if $$ then, for any $k$-assignment $L$, the number of $L$-colorings of a signed graph $Sigma$ with $m$ edges is at least the number of the proper $k$-colorings of $Sigma$. Further, if $L$ is $0$-free (resp., $0$-included) and $k$ is even (resp., odd), then the lower bound $$ for $k$ can be improved to $(m-1)/ln(1+sqrt2)$.

Review text

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.

Recommendations

• Mathematical theories of traffic flow
• Modeling, estimation, and their applications for distributed parameter systems
• scientific article; zbMATH DE number 5055270
• Lefschetz's principle
• Superheating behavior in a breakdown reactor
• scientific article; zbMATH DE number 3188569
• scientific article; zbMATH DE number 3133698
• Pointwise Bounds for Solutions of Semilinear Parabolic Equations

Cites work

• An abstraction of Whitney's broken circuit theorem
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• On the number of list‐colorings
• Signed graph coloring
• Signed graphs
• The chromatic number of a signed graph
• The chromatic polynomial and list colorings
• The odd-valued chromatic polynomial of a signed graph
• When does the list-coloring function of a graph equal its chromatic polynomial

Cited in

(1)

• Bounding the list color function threshold from above

This page was built for publication: The list-coloring function of signed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6136674)