arxiv: 2605.10861 · v1 · submitted 2026-05-11 · 🧮 math.CO

Recognition: 2 theorem links

· Lean Theorem

Enumeratively Chromatic-Choosable Theta Graphs

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

Authors on Pith no claims yet

Pith reviewed 2026-05-12 03:59 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C15

keywords theta graphlist color functionchromatic polynomialenumerative chromatic choosabilityDP-coloringlist coloringchromatic choosability

0 comments

The pith

The paper characterizes exactly which theta graphs satisfy P_ℓ(G,m) = P(G,m) for every positive integer m.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper determines the precise theta graphs for which the list color function equals the chromatic polynomial at every natural number m. These are the enumeratively chromatic-choosable theta graphs, a condition stronger than ordinary chromatic choosability because the actual numbers of proper colorings must coincide under list assignments and under ordinary colorings. Theta graphs consist of two vertices joined by three internally disjoint paths and have served as test cases in list coloring since they appear in characterizations of chromatic-choosable graphs with chromatic number 2. A reader would care because the result settles the enumerative question completely for this family and demonstrates that DP-coloring arguments can establish equality of the two counting functions. The proof proceeds by using the more general DP-coloring setting both to confirm the equality on the graphs that satisfy it and to exhibit failures on the others.

Core claim

The authors characterize the enumeratively chromatic-choosable theta graphs as the exact subfamily for which the list color function P_ℓ(G,m) equals the chromatic polynomial P(G,m) for all m, with the proof relying on DP-coloring to establish both the equality for the graphs that work and the strict inequality for the remaining theta graphs.

What carries the argument

DP-coloring (correspondence coloring), which replaces list assignments with matchings between color sets on adjacent vertices and thereby supplies a counting argument that forces P_ℓ(G,m) = P(G,m) precisely on the identified theta graphs.

If this is right

The identified theta graphs are exactly those for which every m-list assignment admits exactly P(G,m) proper colorings.
DP-coloring supplies both the positive and negative cases in the characterization.
Theta graphs whose three paths meet the structural conditions of the characterization inherit the enumerative equality.
The result enlarges the collection of graphs whose list-color counting functions are known to coincide with their chromatic polynomials.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar DP-coloring counting arguments may classify enumeratively chromatic-choosable graphs inside larger families that contain theta graphs as building blocks.
The structural conditions on path lengths or parities that appear in the characterization could be tested computationally on small examples to verify the boundary between equality and inequality.
If the characterization depends on ratios or differences among the three path lengths, it may suggest analogous ratio-based conditions for enumerative choosability in other minor-closed graph classes.

Load-bearing premise

The DP-coloring construction must correctly imply that the number of proper list colorings equals the number of ordinary colorings exactly on the theta graphs singled out by the characterization, with no other theta graphs accidentally satisfying the equality.

What would settle it

A concrete theta graph outside the characterized family for which direct computation shows P_ℓ(G,m) = P(G,m) at some m, or a graph inside the family for which the two polynomials differ at some m.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper pins down exactly which theta graphs satisfy P_ℓ(G,m) = P(G,m) for all m, using DP-coloring for the positive cases and explicit lists for the rest.

read the letter

The main point is that the authors have characterized all enumeratively chromatic-choosable theta graphs. They find exactly which ones satisfy P_ℓ(G,m) = P(G,m) for all natural numbers m. This is new because previous work on theta graphs covered ordinary chromatic choosability, but the enumerative strengthening with the list color function is fresh. They do a good job applying DP-coloring to prove the equality holds in the right cases by matching correspondence colorings to the chromatic polynomial. For the other cases, explicit lists show the strict inequality. The analysis of path length triples looks complete, with proper handling of subgraphs and no circular reasoning. The argument avoids circularity by importing the DP framework appropriately. Small cases and reductions seem checked out. A minor concern might be whether all possible configurations are covered without oversight, but the case breakdown appears thorough. The paper stays focused on the characterization without overclaiming. Credit is due for the clean application of DP-coloring here, as it directly addresses the list version without extra assumptions. The citation pattern seems standard for the area, building on known theta graph results. This work is for graph theorists working on list coloring and choosability problems. It provides a solid example and benchmark for future studies on when list and ordinary polynomials coincide. It deserves a serious referee because the result is precise and the methods are grounded. I would send this to peer review.

Referee Report

0 major / 2 minor

Summary. The paper characterizes the enumeratively chromatic-choosable theta graphs: those theta graphs G for which the list color function P_ℓ(G,m) equals the ordinary chromatic polynomial P(G,m) for every natural number m. The authors identify precisely which theta graphs (defined by triples of path lengths between two vertices) satisfy the equality, proving the positive cases via DP-coloring (correspondence colorings that reproduce the ordinary count) and the negative cases via explicit list assignments that force strict inequality. The argument proceeds by exhaustive case analysis on the path-length triples, with reductions to smaller subgraphs.

Significance. If the result holds, the paper delivers a complete, explicit characterization within the theta-graph family, extending earlier work on chromatic-choosable graphs of chromatic number 2 and supplying another concrete demonstration that DP-coloring techniques can resolve questions about list-color functions. The case analysis appears exhaustive and the reductions are handled without circularity, which strengthens the contribution to enumerative combinatorics and list-coloring theory.

minor comments (2)

The abstract states that theta graphs 'appear in the characterization of chromatic-choosable graphs with chromatic number 2,' but does not cite the specific reference; adding the citation would improve context.
Notation for the three path lengths (e.g., a,b,c) is introduced in the main theorem but could be defined once in the introduction for readers who skip directly to the statement.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and for recommending acceptance. We are pleased that the characterization of enumeratively chromatic-choosable theta graphs, the DP-coloring arguments for the positive cases, and the explicit constructions for the negative cases were viewed as complete and rigorous.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper characterizes enumeratively chromatic-choosable theta graphs by determining precisely when P_ℓ(G,m) equals P(G,m) for all natural numbers m. It deploys DP-coloring (correspondence coloring) to prove equality holds for the identified graphs via explicit matchings to the ordinary chromatic polynomial, while using direct list assignments to show strict inequality for the complementary cases. The case analysis on path-length triples is exhaustive, with reductions to smaller subgraphs handled via standard inductive or recursive arguments that do not rely on self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations. The invocation of the more general DP-coloring framework to resolve a list-coloring question is an independent strengthening rather than a circular reduction, and no ansatz, uniqueness theorem, or renaming of known results is smuggled in via self-reference.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests entirely on standard definitions from graph theory and the established DP-coloring framework; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)

standard math Standard definitions of graphs, paths, theta graphs, chromatic number, list chromatic number, chromatic polynomial, and list color function.
These are the foundational objects used throughout the paper.
domain assumption DP-coloring (correspondence coloring) is a valid generalization of list coloring.
The proof strategy relies on this established generalization.

pith-pipeline@v0.9.0 · 5510 in / 1164 out tokens · 65791 ms · 2026-05-12T03:59:45.965351+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We characterize the enumeratively chromatic-choosable theta graphs... Our proof utilizes ideas from DP-coloring... P_ℓ(G,m)=P(G,m) for every m∈N.
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 4. Suppose G=Θ(l1,l2,l3)... G is not enumeratively chromatic-choosable if and only if l1,l2,l3 all have the same parity and {l1,l2,l3}≠{2}.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

[1]

Allred and J

S. Allred and J. A. Mudrock. Enumerative chromatic choosability. arXiv:2505.05662,

work page arXiv
[2]

Beier, J

J. Beier, J. Fierson, R. Haas, H. M. Russell, and K. Shavo. Classifying coloring graphs. Discrete Math., 339(8):2100–2112, 2016

work page 2016
[3]

Biggs.Algebraic graph theory

N. Biggs.Algebraic graph theory. Cambridge Mathematical Library. Cambridge Univer- sity Press, Cambridge, second edition, 1993

work page 1993
[4]

G. D. Birkhoff. A determinant formula for the number of ways of coloring a map.Ann. of Math. (2), 14(1-4):42–46, 1912

work page 1912
[5]

J. I. Brown, C. A. Hickman, A. D. Sokal, and D. G. Wagner. On the chromatic roots of generalized theta graphs.J. Combin. Theory Ser. B, 83:272–297, 2001

work page 2001
[6]

M. V. Bui, H. Kaul, M. Maxfield, J. A. Mudrock, P. Shin, and S. Thomason. Non- chromatic-adherence of the DP color function via generalized theta graphs.Graphs Combin., 39(3):Paper No. 42, 2023

work page 2023
[7]

J. M. Carraher, T. Mahoney, G. J. Puleo, and D. B. West. Sum-paintability of generalized theta-graphs.Graphs Combin., 31(5):1325–1334, 2015

work page 2015
[8]

Dong and M

F. Dong and M. Zhang. An improved lower bound ofP(G, L)−P(G, k) fork-assignments L.J. Combin. Theory Ser. B, 161:109–119, 2023. 10

work page 2023
[9]

Q. Donner. On the number of list-colorings.J. Graph Theory, 16:239–245, 1992

work page 1992
[10]

Dvoˇ r´ ak and L

Z. Dvoˇ r´ ak and L. Postle. Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8.J. Combin. Theory Ser. B, 129:38–54, 2018

work page 2018
[11]

Erd¨ os, A

P. Erd¨ os, A. L. Rubin, and H. Taylor. Choosability in graphs. InProceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), volume XXVI ofCongress. Numer., pages 125–157. Utilitas Math., Winnipeg, MB, 1980

work page 1979
[12]

H¨ aggkvist and A

R. H¨ aggkvist and A. Chetwynd. Some upper bounds on the total and list chromatic numbers of multigraphs.J. Graph Theory, 16(5):503–516, 1992

work page 1992
[13]

Halberg, H

C. Halberg, H. Kaul, A. Liu, J. A. Mudrock, P. Shin, and S. Thomason. On polynomial representations of the DP color function: theta graphs and their generalizations.J. Comb., 15(4):451–468, 2024

work page 2024
[14]

H. Kaul, A. Kumar, A. Liu, J. A. Mudrock, P. Rewers, P. Shin, M. S. Tanahara, and K. To. Bounding the list color function threshold from above.Involve, 16(5):849–882, 2023

work page 2023
[15]

Kaul and J

H. Kaul and J. A. Mudrock. On the chromatic polynomial and counting DP-colorings of graphs.Adv. Appl. Math., 123:103121, 2021

work page 2021
[16]

Kirov and R

R. Kirov and R. Naimi. List coloring andn-monophilic graphs.Ars Combin., 124:329– 340, 2016

work page 2016
[17]

A. V. Kostochka and A. Sidorenko. Problem session of the prachatice conference on graph theory. InFourth Czechoslovak Symposium on Combinatorics, Graphs and Complexity, volume 51, page 380. 1992

work page 1992
[18]

Laiche, I

D. Laiche, I. Bouchemakh, and ´E. Sopena. On the packing coloring of undirected and oriented generalized theta graphs.Australas. J. Combin., 66:310–329, 2016

work page 2016
[19]

R. Li, H. Broersma, and S. Zhang. Properly edge-colored theta graphs in edge-colored complete graphs.Graphs Combin., 35:261–286, 2019

work page 2019
[20]

J. A. Mudrock, M. Marsh, and T. Wagstrom. On list equitable total colorings of the generalized theta graph.Discuss. Math. Graph Theory, 41:1215–1233, 2021

work page 2021
[21]

K. Ohba. On chromatic-choosable graphs.J. Graph Theory, 40(2):130–135, 2002

work page 2002
[22]

Sathiamoorthy and T

G. Sathiamoorthy and T. N. Janakiraman. Graceful labeling of generalized theta graphs. Proc. Natl. Acad. Sci. Lett., 41(2):121–122, 2018

work page 2018
[23]

A. D. Sokal. Chromatic roots are dense in the whole complex plane.Combin. Probab. Comput., 13:221–261, 2004. 11

work page 2004
[24]

Thomassen

C. Thomassen. The chromatic polynomial and list colorings.J. Combin. Theory Ser. B, 99:474–479, 2009

work page 2009
[25]

V. G. Vizing. Coloring the vertices of a graph in prescribed colors.Diskret. Analiz, 101(29):3–10, 1976

work page 1976
[26]

W. Wang, J. Qian, and Z. Yan. When does the list-coloring function of a graph equal its chromatic polynomial.J. Combin. Theory Ser. B, 122:543–549, 2017

work page 2017
[27]

D. B. West.Introduction to graph theory. Prentice Hall, Inc., Upper Saddle River, NJ, 2001. 12

work page 2001