A Polynomial Method for Counting Colorings of Sparse Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909355210702848 |
|---|---|
| author | Dahlberg, Samantha L. Kaul, Hemanshu Mudrock, Jeffrey A. |
| author_facet | Dahlberg, Samantha L. Kaul, Hemanshu Mudrock, Jeffrey A. |
| contents | The notion of $S$-labeling of graphs, where $S$ is a subset of a symmetric group, was introduced in 2019 by Jin, Wong, and Zhu. This notion provides the framework for a common generalization of various well studied notions of graph coloring, including classical coloring, signed $k$-coloring, signed $\mathbb{Z}_k$-coloring, DP (or correspondence) coloring, group coloring, and coloring of gained graphs. In this paper, we present a unified and simple polynomial method for giving exponential lower bounds on the number of colorings of an $S$-labeled graph for all such $S$. This algebraic technique allows us to prove new lower bounds on the number of colorings of any $S$-labeling of graphs satisfying certain sparsity conditions. We also investigate how the structure of $S$ can be exploited to improve the applicability of these bounds. Our results give new lower bounds on the number of DP-colorings, and consequently the number of all types of colorings listed above. This includes the chromatic polynomial and the number of list colorings of families of planar graphs, and the number of colorings of signed graphs. These enumerative bounds improve previously known results or are the first such known results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_11744 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Polynomial Method for Counting Colorings of Sparse Graphs Dahlberg, Samantha L. Kaul, Hemanshu Mudrock, Jeffrey A. Combinatorics 05C15, 12E10, 05C25, 05C30, 05C31, 05A99 The notion of $S$-labeling of graphs, where $S$ is a subset of a symmetric group, was introduced in 2019 by Jin, Wong, and Zhu. This notion provides the framework for a common generalization of various well studied notions of graph coloring, including classical coloring, signed $k$-coloring, signed $\mathbb{Z}_k$-coloring, DP (or correspondence) coloring, group coloring, and coloring of gained graphs. In this paper, we present a unified and simple polynomial method for giving exponential lower bounds on the number of colorings of an $S$-labeled graph for all such $S$. This algebraic technique allows us to prove new lower bounds on the number of colorings of any $S$-labeling of graphs satisfying certain sparsity conditions. We also investigate how the structure of $S$ can be exploited to improve the applicability of these bounds. Our results give new lower bounds on the number of DP-colorings, and consequently the number of all types of colorings listed above. This includes the chromatic polynomial and the number of list colorings of families of planar graphs, and the number of colorings of signed graphs. These enumerative bounds improve previously known results or are the first such known results. |
| title | A Polynomial Method for Counting Colorings of Sparse Graphs |
| topic | Combinatorics 05C15, 12E10, 05C25, 05C30, 05C31, 05A99 |
| url | https://arxiv.org/abs/2312.11744 |