Enumeratively Chromatic-Choosable Theta Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913112858296320 |
|---|---|
| author | Chi, Yanghong Lee, Seoju Morrissette, Fennec Mudrock, Jeffrey A. Nguyen, Gavin Whatley, Benjamin |
| author_facet | Chi, Yanghong Lee, Seoju Morrissette, Fennec Mudrock, Jeffrey A. Nguyen, Gavin Whatley, Benjamin |
| contents | Chromatic choosability is a notion of fundamental importance in list coloring. A graph $G$ is chromatic-choosable when its chromatic number, $χ(G)$, is equal to its list chromatic number $χ_{\ell}(G)$. In 1990, Kostochka and Sidorenko introduced the list color function of a graph $G$, denoted $P_{\ell}(G,m)$, which is the list analogue of the chromatic polynomial of $G$, $P(G,m)$. A graph $G$ is said to be enumeratively chromatic-choosable when $P_{\ell}(G,m)=P(G,m)$ for every $m \in \mathbb{N}$. Theta graphs and their generalizations have played an important role in graph coloring problems over the years; for example, they appear in the characterization of chromatic-choosable graphs with chromatic number 2. In this paper we characterize the enumeratively chromatic-choosable theta graphs. Our proof utilizes ideas from DP-coloring (a.k.a. correspondence coloring), providing yet another example of how the more general setting of DP-coloring can be leveraged to attack a problem in list coloring. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_10861 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Enumeratively Chromatic-Choosable Theta Graphs Chi, Yanghong Lee, Seoju Morrissette, Fennec Mudrock, Jeffrey A. Nguyen, Gavin Whatley, Benjamin Combinatorics 05C15, 05C30 Chromatic choosability is a notion of fundamental importance in list coloring. A graph $G$ is chromatic-choosable when its chromatic number, $χ(G)$, is equal to its list chromatic number $χ_{\ell}(G)$. In 1990, Kostochka and Sidorenko introduced the list color function of a graph $G$, denoted $P_{\ell}(G,m)$, which is the list analogue of the chromatic polynomial of $G$, $P(G,m)$. A graph $G$ is said to be enumeratively chromatic-choosable when $P_{\ell}(G,m)=P(G,m)$ for every $m \in \mathbb{N}$. Theta graphs and their generalizations have played an important role in graph coloring problems over the years; for example, they appear in the characterization of chromatic-choosable graphs with chromatic number 2. In this paper we characterize the enumeratively chromatic-choosable theta graphs. Our proof utilizes ideas from DP-coloring (a.k.a. correspondence coloring), providing yet another example of how the more general setting of DP-coloring can be leveraged to attack a problem in list coloring. |
| title | Enumeratively Chromatic-Choosable Theta Graphs |
| topic | Combinatorics 05C15, 05C30 |
| url | https://arxiv.org/abs/2605.10861 |