The list-coloring function of signed graphs

DOI10.1016/J.DISC.2023.113790arXiv2207.05262OpenAlexW4388812527MaRDI QIDQ6136674FDOQ6136674

Authors: Sumin Huang, Jianguo Qian, Wei Wang 

Publication date: 17 January 2024

Published in: Discrete Mathematics (Search for Journal in Brave)

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

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

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
• Pointwise Bounds for Solutions of Semilinear Parabolic Equations

zbMATH Keywords

list coloringsigned graphnumber of list colorings

Mathematics Subject Classification ID

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

Cites Work

• Signed graphs
• Signed graph coloring
• Title not available (Why is that?)
• The chromatic number of a signed graph
• The chromatic polynomial and list colorings
• When does the list-coloring function of a graph equal its chromatic polynomial
• On the number of list‐colorings
• An abstraction of Whitney's broken circuit theorem
• The odd-valued chromatic polynomial of a signed graph

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)