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 coloringsigned graphnumber of list colorings

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)$.

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

• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• An abstraction of Whitney's broken circuit theorem
• 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)