EUVIMEDEUVIMED entdecken
Crossref

Enumeratively chromatic-choosable theta graphs

Yanghong Chi, Seoju Lee, Fennec Morrissette, Jeffrey Mudrock, Gavin Nguyen, Benjamin Whatley

Enumerative Combinatorics and Applications · 24.04.2026 · 6 (3) · Article #S2R23

DOI: 10.54550/eca2026v6s3r23 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Enumerative Combinatorics and Applications, online erschienen am 24.04.2026. Verfasst von Yanghong Chi und 5 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Chromatic choosability is a notion of fundamental importance in list coloring. A graph $G$ is chromatic-choosable when its chromatic number, $\chi(G)$, is equal to its list chromatic number $\chi_{\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.

Zitieren

APA

Chi, Y., Lee, S., Morrissette, F., Mudrock, J., Nguyen, G., & Whatley, B. (2026). Enumeratively chromatic-choosable theta graphs. Enumerative Combinatorics and Applications, 6(3), Article #S2R23. https://doi.org/10.54550/eca2026v6s3r23

Vancouver

Chi Y, Lee S, Morrissette F, Mudrock J, Nguyen G, Whatley B. Enumeratively chromatic-choosable theta graphs. Enumerative Combinatorics and Applications. 2026;6(3):Article #S2R23. doi:10.54550/eca2026v6s3r23

BibTeX
@article{Chi2026,
  author = {Chi, Yanghong and Lee, Seoju and Morrissette, Fennec and Mudrock, Jeffrey and Nguyen, Gavin and Whatley, Benjamin},
  title = {Enumeratively chromatic-choosable theta graphs},
  journal = {Enumerative Combinatorics and Applications},
  year = {2026},
  volume = {6},
  number = {3},
  pages = {Article #S2R23},
  doi = {10.54550/eca2026v6s3r23}
}
Kostenlos starten →