Hemanshu Kaul: Papers and Talks
Papers and Publications
Papers and Publications by Research Topics:

Book:
 Advances in Interdisciplinary Applied Discrete Mathematics, (coeditor with H.M. Mulder), Interdisciplinary Mathematical Sciences, Volume 11, World Scientific Publishing, 2010, 275pp.
Here is the book's Cover, Title Page, and Introduction.
Available at the Publisher's site, and on Amazon.

Papers on Optimization, Algorithms, and Mathematical Modeling:
 Global Optima Results for the Kauffman NK Model, (with S.H. Jacobson),
Mathematical Programming, Volume 106, 2006, 319338.
summary:
The Kauffman NK model is a stochastic combinatorial optimization model that has been used in theoretical biology, physics and management science to model complex systems with interacting components. It could be crudely described as an optimization problem to find a maximum valued (weighted) pnary vector of length N with the value (weight) of a vector defined in terms of its components' weights and their `interaction' with K `neighboring' components.
This paper analyzes global optima of the NK model. Most previous papers focused on local optima and simulation based results. We transform this NPhard global optimization problem into a stochastic network model that is closely related to two wellstudied problems in operations research  project duration in PERT networks and stochastic shortest path problem. This transformation leads to applicable strategies for explicit computation of bounds on the global optima (particularly with K either small or close to N), such as a recursive scheme applicable as a dynamic program and simple stochastic networks that can be processed simultaneously. A general lower bound, which is sharp for K=0, is obtained for the expected value of the global optimum of the NK model in terms of the order statistics of the underlying distribution. We also give a detailed analysis for the expectation and variance of the global optimum when K=N1 and the underlying distribution is the Uniform distribution over [0,1], by converting the analytic problem into a geometric one with estimation of volumes of certain bodies in the Ndimensional hypercube. The lower and upper bounds on the expectation obtained for this case show that there is a wide gap between the values of the local and the global optima. They also indicate that the complexity catastrophe, the tendency of the local optima to collapse towards average behavior, does not arise for the global optima
 New Global Optima Results for the Kauffman NK Model: Handling Dependency, (with S.H. Jacobson),
Mathematical Programming, Special issue on 'Optimization under Uncertainty', Volume 108, 2006, 475494.
summary:
This paper generalizes and extends the work from the previous paper that focused on the analysis of the
(independent) case K=N1. It presents new global optima results for the NK model by developing
tools for handling the dependency between weight functions of different Nvectors due to overlapping weight
contributions from their components. Previous papers used Markov chain theory to analyze the cases when K=1, N tends to infinity and the underlying distributions are exponential or negative exponential. The ideas developed here are more combinatorial in nature, independent of specific underlying distributions and especially applicable to K growing with N.
We define and study a dependency graph to handle dependencies among underlying random variables in the NK model. Equitable coloring of the dependency graph is used to bound general order statistics (with dependencies) and consequently, the expected value of the global optima, E(N,K), for the NK model. These bounds convert the problem of bounding order statistics of dependent random variables into that of independent random variables while incorporating quantitative information about the mutual dependencies between the underlying random variables. An alternative upper bound on E(N,K) using direct arguments is also proposed. These ideas for handling dependence are applied to give a detailed analysis of E(N,K) for K close to N (K = Na and K = bN) with sharp bounds when the underlying distribution is Normal by using tools from order statistics theory, and when the underlying distribution is Uniform by extending the geometric ideas from the first paper for bounding volumes of appropriate bodies. Finally, for bounded underlying distributions, the global optima is shown to be concentrated around its mean E(N,K).
 Analyzing the Performance of Simultaneous Generalized Hill Climbing Algorithms, (with D.E. Vaughan and S.H. Jacobson), Computational Optimization and Applications, Volume 37, 2007, 103119.
summary:
Simultaneous generalized hill climbing (SGHC) algorithms provide a framework for using heuristics to
simultaneously address sets of intractable discrete optimization problems where information is shared between
the problems during the algorithm execution. A SGHC algorithm probabilistically moves between discrete
optimization problems during its execution according to a (problem generation) probability function. Many
wellknown heuristics (Generalized Hill Climbing (GHC) algorithms), including simulated annealing, threshold
accepting and pure local search, can be embedded within the SGHC algorithm framework.
This paper shows that the solutions generated by an SGHC algorithm are a stochastic process that satisfies the
Markov property. This allows the problem probability mass functions to be formulated for particular sets of
problems based on the longterm behavior of the algorithm. Such results can be used to determine the proportion
of iterations that an SGHC algorithm will spend optimizing over each discrete optimization problem. Sufficient
conditions that guarantee that the algorithm spends an equal number of iterations in each discrete optimization
problem are provided. SGHC algorithms can also be formulated such that the overall performance of the algorithm
is independent of the initial discrete optimization problem chosen. Sufficient conditions are obtained
guaranteeing that an SGHC algorithm will visit the globally optimal solution for each discrete optimization
problem. Lastly, rates of convergence for SGHC algorithms are reported that show that given a rate of
convergence for the embedded GHC algorithm, the SGHC algorithm can be designed to preserve this rate.
 Long Local Searches for Maximal Bipartite Subgraphs, (with D.B. West), SIAM Journal on Discrete Mathematics, Volume 22, 2008, 11381144.
summary:
We study a wellknown localsearch algorithm for finding a bipartite subgraph with maximum number of edges in a
given graph. Starting with an arbitrary vertex partition, move (`flip') a vertex from one partite set to the
other if doing so increases the number of edges in the cut. We improve the previous bestknown lower bound,
(1/2)n^{(3/2)}, on the maximum number of flips possible in a graph with n vertices to
(2/25)n^{2}. Note that (1/4)n^{2} is a trivial upper bound. We also prove better upper bounds
like [E(G)(1/4)d^{2}], in terms of d the minimum degree of the graph. We also show that the minimum
number of flips needed to reach a global optimum ≤ n/2, answering a question of Cowen and West.
 Reductions for the Stable Set Problem, (with E.C. Sewell and S.H. Jacobson), Algorithmic Operations Research, Vol 6(1), 2011, 4055.
summary:
One approach to finding a maximum stable (independent) set (MSS) (or, equivalently a maximum clique or a
minimum vertex cover) in a graph is to try to reduce the size of the problem by transforming the problem into
an equivalent problem on a smaller graph. These reductions have been used to study properties of stability
critical graphs and facets of the stable set polytope. They have also been used algorithmically in heuristics,
polynomialtime algorithms for special classes of graphs, and exact algorithms.
This paper introduces several new reductions for the MSS problem, extends several well known reductions to the
maximum weight stable set (MWSS) problem, demonstrates how reductions for the generalized stable set problem
can be used in conjunction with probing to produce powerful new reductions for both the MSS and MWSS problems,
and shows how hypergraphs can be used to expand the capabilities of clique projections. The effectiveness of
these new reduction techniques are illustrated on a set of challenging MSS problems arising from Steiner Triple
Systems.
 Maximum SeriesParallel Subgraph: Approximation Algorithms, (with G. Calinescu and C.G. Fernandes),
Algorithmica, Vol 63, 2012, 137157.
summary:
Consider the NPhard problem of, given a simple graph G, to find a K_{4}minorfree subgraph (seriesparallel subgraph) of G with the maximum number of edges. The algorithm that, given a connected graph G, outputs a spanning tree of G, is a (1/2)approximation. Indeed, if n is the number of vertices in G, any spanning tree in G has (n1) edges and any seriesparallel graph on n vertices has at most (2n3) edges.
We present a (7/12)approximation algorithm (current best) for this problem and, constructions and computational complexity results showing the limits of our approach. Unlike earlier algorithms for various planar subgraph problems, the subgraph we generate is neither a tree nor an outerplanar graph. For the first time, we are able to analyze an algorithm that allows blocks of unbounded size in solution subgraph and is allowed to shrink or throw away previously selected blocks.
 Approximating the Quadratic Knapsack Problem and its Generalization, (with S. Kapoor and M. Pelsmajer), technical report.
summary:
We consider a reformulation of the Quadratic Knapsack Problem, the Graph Knapsack Problem where a given graph G (and similarly its generalization, the Hypergraph Knapsack Problem with an underlying hypergraph) has weights on vertices and benefits on edges and vertices. Given a budget bound W the goal is to identify a subset of vertices having total weight at most W such that the benefit of the induced subgraph (similarly, subhypergraph) is maximized. These problems generalize many graph optimization problems and other generalizations of the Knapsack problem such as Knapsack Problem with Conflict Graph, Constrained Knapsack Problem, PrecedenceConstrained Knapsack Problem, and SubsetUnion Knapsack Problem, which are all NPhard and most are even hard to approximate. In particular they generalize the Quadratic Knapsack Problem as well as the dense ksubgraph problem and arise naturally in the context of resource allocation in transportation systems.
We give examples that show that algorithms proposed for Classical Knapsack problem and the Heaviest subgraph problem behave poorly when applied to GKP. We give a FPTAS (Fully Polynomial Time Approximation Scheme) when the underlying graph has bounded Treewidth. We can also generalize this result to the Hypergraph version of the GKP, where the dependencies between items are not just pairwise but kwise for any k ≥ 2.
 New Methodology for Transportation Investment Decisions with Consideration of Project Interdependencies, (with Z. Li, S. Kapoor, and E. Veliou^, B. Zhou^, C. Lee^), Transportation Research Record: Journal of the Transportation Research Board of the National Academies, Issue 2285, 2012, 3646.
summary:
We introduce a new model and algorithms for optimal highway investment decisionmaking to support sustainable transportation. The objective is to decide which highway projects to invest in and implement, such that total utility of the highway transportation network after project implementation viewed from economic (total cost to the transportation agency and the user), social (traffic mobility and safety), and environmental (energy consumption and vehicle emissions) dimensions is maximized. In the past, decisions were based on calculating the benefit of each highway project independently, by measuring its local impacts. However, this ignores two important factors. Firstly, local changes in a transportation network can lead to agglomerative changes in its global behavior. An addition or expansion of a single road segment can lead to better (or sometimes worse) traffic conditions elsewhere even far away from it. Secondly, multiple projects within a certain geographical area or a major corridor of the transportation network may be proposed for implementation simultaneously, which means that such projects cannot be considered independent of each other. For the first time, this research takes both these factors into account in the new models that have been proposed.
The benefit of a collection of projects is defined in terms of an appropriate multicommodity flow problem defined over the highway network under study with different nonlinear cost functions. These benefits satisfy the global dependence properties described above. These benefits are used to calculate the data needed for Graph Knapsack Problem, which is then solved to give an appropriate solution for the highwayinvestment decisionmaking.
We complete a computational study of the road network in the Chicago downtown loop area using latest reallife traffic data from IDOT (Illinois Department of Transportation) to analyze the decisionmaking for multiple projects under consideration there. Our results clearly show that our models capture the effects of dependency between different projects. Ignoring these effects gives a false inflated benefit from a collection of projects leading to erroneous decisionmaking.
 Approximating 01 Quadratic Programming using Second Order Cone Programs, (with S. Kapoor), technical report.
summary:
We consider the problem of approximating Quadratic 01 Integer Programs with nonnegative integer constraint matrix entries, which we term as PIQP. Our approximation is based on a program with hyperbolic constraints (a SecondOrder Cone Programming SOCP formulation) that achieves an approximation ratio of O(a(max) (n/b(n))), where a(max) is the maximum size of an entry in the constraint matrix defined by constraints a_{i}^{T}X ≤ W_{i}, for all i, and b(n) ≤ max{W_{i}}. By appropriately choosing b(n), the randomized algorithm, when combined with other algorithms that achieve good approximations for larger values of b(n), allows better algorithms for the complete range of W_{i}. Our solution is achieved by a randomization of the optimal solution to the relaxed version of the hyperbolic program. We show that this solution provides the approximation bounds using nonlinear concentration of measure bounds studied by Kim and Vu. The bounds achieved, together with a greedy algorithm, provide a O*(a(max) n^{1/2}) factor approximation, where O* hides logarithmic terms.
 A Public Transit Network Optimization Model for Equitable Access to Social Services, (with A. Rumpf^), refereed conference version in ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization 2021 (EAAMO '21), Article 16, 2021, 117..
summary:
The primary focus of this paper is to consider a problem which is in some ways the inverse of the classical facility location problem: rather than changing facility locations in a fixed transit network, we consider changing a transit network containing fixed facility locations. This can improve accessibility levels in the same way that placing facilities can, since reducing travel times makes effective catchment areas larger and brings fast access to more communities. Public transit planning can also be implemented much more immediately since tactical decisions like bus frequency setting can be enacted without the need for permanent changes to the infrastructure.
We present a flexible public transit network design model which optimizes a social access objective while guaranteeing that the system’s costs and transit times remain within a preset margin of their current levels. The purpose of the model is to find a set of minor, immediate modifications to an existing bus network that can give more communities access to the chosen social services while having a minimal impact on the current network’s operator costs and user costs. Design decisions consist of reallocation of existing resources in order to adjust line frequencies and capacities. We present a hybrid tabu search/simulated annealing algorithm for the solution of this optimizationbased model. As a case study we apply the model to the problem of improving equity of access to primary health care facilities in the Chicago metropolitan area. The results of the model suggest that it is possible to achieve better primary care access equity through reassignment of existing buses and implementation of express runs, while leaving overall service levels relatively unaffected.
 A Linear Input Dependence Model for Interdependent Networks, (with A. Rumpf^), European Journal of Operational Research, Volume 302, 2022, 781797.
summary:
We consider a linear relaxation of a generalized minimumcost network flow problem with binary input dependencies. In this model the flows through certain arcs are bounded by linear (or more generally, piecewise linear concave) functions of the flows through other arcs. This formulation can be used to model interrelated systems in which the components of one system require the delivery of material from another system in order to function (for example, components of a subway system may require delivery of electrical power from a separate system). We propose and study randomized rounding schemes for how this model can be used to approximate solutions to a related mixed integer linear program for modeling binary input dependencies. The introduction of side constraints prevents this problem from being solved using the wellknown network simplex algorithm, however by characterizing its basis structure we develop a generalization of network simplex algorithm that can be used for its computationally efficient solution. If the number of interdependencies is sufficiently small in comparison to the size of the overall network, we can even achieve a running time that approaches that of network simplex, in spite of the fact that network simplex cannot be directly applied to this problem.
 Longitudinal network models and permutationuniform Markov chains, (with W. Schwartz^, and S. Petrovic), Scandinavian Journal of Statistics, Volume 50, 2023, 12011231.
summary:
We offer a general approach to modeling longitudinal network data, including exponential random graph models (ERGMs), that vary according to certain discretetime Markov chains. We connect conditional and Markovian exponential families, permutationuniform Markov chains, various (temporal) ERGMs, and statistical considerations such as dyadic independence and exchangeability. By removing models’ temporal dependence but not interpretability, our approach simplifies analysis of some network and autoregressive models from the literature, including closedform expressions for maximum likelihood estimators. We also introduce exponential random tmultigraph models, motivated by our result on replacing t observations of permutationuniform Markov chains of graphs with single observations of corresponding multigraphs.
 An Improved Algorithm for Finding Maximum Outerplanar
Subgraphs, (with Gruia Calinescu, and Bahareh Kudarzi^), Discrete Applied Mathematics, Volume 342, 2024, 207217.
summary:
Given a graph G, finding an outerplanar subgraph of G with the maximum number of edges is called the Maximum Outerplanar Subgraph problem. While outerplanar graphs have been investigated indepth for their applications and theoretical properties, the problem of finding large outerplanar subgraphs of a graph has not been studied as much. Most problems which are NPhard on arbitrary graphs become polynomial on outerplanar graphs. An indepth exploration of practical algorithms for Maximum Outerplanar Subgraph was done by Poranen in 2005. His main experimental result is that simulated annealing with initial solution taken from the greedy triangular cactus approximation algorithm yields the best known heuristic for the Maximum Outerplanar Subgraph problem.
Maximum Outerplanar Subgraph problem is NPhard. Hence, instead of solving the problem exactly, we develop polynomialtime approximation algorithms. By constructing a spanning tree of a given graph, one obtains an approximation ratio for the Maximum Outerplanar Subgraph problem of 1/2. The approximation ratio was improved by Calinescu, Fernandes, Finkler, and Karloff (1998) by using the concept of triangular cactus. The greedy triangular cactus approximation algorithm results in a nontrivial approximation ratio of 7/12. Furthermore, using the fact that computing a triangular cactus with maximum number of triangles can be done in polynomial time based on Matroid Parity to obtain a 2/3 approximation ratio.
We develop a (7/10)approximation algorithm by adding appropriate induced 4cycles to a triangular cactus. While the algorithm is very simple (except for the use of Matroid Parity), the tight analysis we provide is nice and elementary, and may have wider applications. Applying a greedy method after matching methods (Matroid Parity is an extension of graph matching) is new to us; applying matching methods after greedy methods has been done before. We discuss that adding pentagons or larger outerplanar graphs beyond the induced 4cycles would not improve the approximation ratio.

Papers on Extremal Graph Theory:
 Extremal Graphs for a Graph Packing Theorem of Sauer and Spencer, (with A. Kostochka), Combinatorics, Probability and Computing, Volume 16, 2007, 409417.
summary:
Let G, H be graphs with maximum degrees D(G), D(H), and orders n(G), n(H) at most n. G and H are said to pack if there exist injective mappings of the vertex sets into [n], such that the images of the edge sets do not intersect. In other words, either G or H is isomorphic to a subgraph of the complement of the other. The concept of graph packing generalizes various extremal graph problems, including problems on existence of fixed subgraphs (such as the Hamiltonian Cycle problem), forbidden subgraphs (Turantype problems), and equitable coloring. One of the classical results in this area was by Sauer and Spencer (1978) : if 2D(G)D(H) < n then G and H pack.
We characterize the graphs that achieve equality in the condition on maximum degrees as given in the SauerSpencer result for packing of graphs. We show that: If 2D(G)D(H) ≤ n, then G and H do not pack if and only if one of G or H is a perfect matching and the other either is a complete bipartite graph of (n/2) vertices in each partite set with (n/2) odd, or contains a complete graph of order (1+ n/2). This gives the SauerSpencer theorem as a corollary. This result can be thought of as small step towards the wellknown BollobasEldridge conjecture (see below).
 On a Graph Packing Conjecture of Bollobas, Eldridge, and Catlin, (with A. Kostochka and G.Yu), Combinatorica, Volume 28, 2008, 469485.
summary:
See the definition of graph packing and related notation in the summary above. One of the earliest results in this area was by Sauer and Spencer (1978) : if 2D(G)D(H) < n then G and H pack. The main conjecture in the area was made by Bollobas and Eldridge in 1978, and independently by Catlin in 1974, as an extension of the SauerSpencer result: if (D(G)+1)(D(H)+1) ≤ n+1 then G and H pack. If true, this conjecture would be sharp, and would be a considerable extension of the HajnalSzemeredi theorem on equitable colorings. The conjecture has only been proved when D(G) ≤ 2, or D(G) = 3 and n is huge, and for some special families of graphs.
This paper focuses on proving a result of the form : for a fixed t in [0,1], (D(G)+1)(D(H) +1) ≤ (n/2)(1+t)+1 implies G and H pack. For t=0, this is essentially the SauerSpencer result, while t=1 gives the BEC conjecture. Thus, for any t>0 this would improve the SauerSpencer result and make progres towards the BEC conjecture. We have proved this result for t=0.2. That is, we have essentially improved the bound on the product of maximum degrees in the SauerSpencer theorem from (0.5)n to (0.6)n. Even in 2020, this remains the best progress towards BollobasEldridgeCatlin conjecture.
 Guarding Orthogonal Art Galleries with Holes, (with Y. Jo^), technical report.
summary:
The original art gallery problem (V. Klee, 1973) asked for the minimum number of guards sufficient to see every point of the interior of an nvertex simple polygon (Art Gallery). Chvatal (1975) proved that (n/3) guards are always sufficient. If all the edges of the given simple polygon are either horizontal or vertical, then such a polygon is called an orthogonal gallery. Kahn, Klawe and Kleitman (1983) proved that (n/4) guards are sufficient for such a nvertex orthogonal gallery. We study orthogonal gallery with holes, i.e., an orthogonal polygon enclosing some other orthogonal polygons called holes (interior of each hole is empty, so these holes model natural obstructions to visibility in the interior of the polygon). In 1982, Shermer conjectured that any orthogonal polygon with n vertices and h holes can be guarded by (n+h)/4 vertex guards. This conjecture remains open. The best previous result shows that (n+2h)/4 such guards suffice (O'Rourke 1987).
We improve this bound to (n+(5/3)h)/4 using a graph coloring argument over a geometric graph. This is still the best known bound.
 Distinguishing Chromatic Number of Cartesian Products of Graphs, (with J. Choi^ and S. Hartke), SIAM Journal on Discrete Mathematics, Volume 24, 2010, 82100.
summary:
The distinguishing chromatic number of a graph G, χ_{D}(G), is the least number of colors needed for a proper coloring of G with the property that the only colorpreserving automorphism of G is the identity. That is, we want to give a proper coloring of a graph that breaks all its symmetries, so that the coloring together with the structure of the graph uniquely determines the vertices. This can be thought of as an exact encoding of the vertices using only a proper coloring. It is a common extension of both the chromatic number and the distinguishing number of graphs.
The chromatic number, χ(G), is an immediate lower bound for χ_{D}(G). We show that χ_{D}(G) can be surprisingly at most one worse than χ(G) for G a Cartesian power of any graph. The main theorem is : For every graph G, there exists a constant d(G) (explicitly given) such that for all d ≥ d(G), χ_{D}(G^{d}) ≤ χ(G)+1, where G^{d} denotes the Cartesian product of d copies of G. Using our proof techniques, we also find the distinguishing chromatic number for Hypercubes, Hamming graphs (Cartesian products of complete graphs), and Cartesian products of complete multipartite graphs.
 Packing of Graphic ntuples, (with A. Busch, M. Ferrara, S. Hartke, M.S. Jacobson, and D.B. West), Journal of Graph Theory, Vol 70, 2012, 2939.
summary:
Let p=(p_{1},...,p_{n}) and q=(q_{1},...,q_{n}) be graphic ntuples (they need not be monotone). We say that p and q pack if there exist edgedisjoint graphs G and H with vertex set v_{1}, ..., v_{n} such that the degrees of v_{i} in G and H are p_{i} and q_{i}, respectively. When packing graphs, we permit permuting the vertices to make G and H "fit together", but when packing sequences, we do not permit the sequences to be permuted. From an optimization pointofview, this can be thought of as an feasibility problem. This problem is related to certain multicommodity flow problems with applications in supply chain/logistics, and even xray tomography. However, packing even 2 bipartite sequences is NPhard.
We prove that two graphic ntuples pack if D ≤ sqrt(2dn)(d1), where D and d denote the largest and smallest entries in p+q (strict inequality when d=1); furthermore, the bound is sharp. If the two graphic sequences do not share any 0 terms then D < sqrt(2n) implies the two sequences pack. This can be thought of as SauerSpencer type of packing result (see the summary of the first packing paper above).
Kundu's Theorem (1973) characterizes when a graphic ntuple has a realization containing a spanning subgraph that is kregular. We consider extensions of Kundu's Theorem and conjecture the stronger statement that in fact when n is even there is a realization containing k edgedisjoint 1factors (that is, a kedgecolorable kfactor). We prove the conjecture when the largest entry is at most 1+(n/2). We also prove the more difficult result that the conjecture holds when k ≤ 3, by proving the stronger statement that there is a realization containing a kfactor that has two edgedisjoint 1factors.
 On Graph FallColoring  Operators and Heredity, (with C. Mitillos^), Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 106 (2018), 125151.
summary:
Graph fallcoloring, also known as Idomatic partition or Independent Domatic partition of graphs, was formally introduced by Dunbar, Hedetniemi, Hedetniemi, Jacobs, Knisely, Laskar and Rall in 2000 as an extension of both graph coloring and graph domination. It asks for a partition of the vertex set of a given graph into independent dominating sets, or equivalently into maximal independent sets. Since a fall coloring of a graph need not always exist, the question of its existence is a fundamental problem.
We study the effect that various graph operators have on fallcolorability. We consider binary graph operators such as the Cartesian, categorical, rooted, strong, and lexicographic products of graphs, as well as the graph join operation. We also study unary graph operators such as the power operators and the related middle and total graph operators, and the generalized Mycielski operators. We apply our results to prove a part of the ErdosFaberLovasz conjecture, as well as reformulate the conjecture in terms of fallcoloring and hypergraphs. We define and study the notion of edit distance of graph to a fallcolorable supergraph using the edge insertion operator, and show that this is an NPcomplete problem.
We see the full spectrum of effects that these graph operators have on fallcolorability.
Preservation of the fall colorability of the input graphs: the Cartesian, rooted, and categorical products.
Modification of the fall colorability: the strong and lexicographic products, the join, and some of the generalized Mycielski operators.
Elimination of the fall colorability: the usual Mycielski operator, as well as repeated applications of the Middle graph operator.
Creation of fall colorability when applied to specific nonfallcolorable graphs: certain power operators, Cartesian power, or by edge insertion.
 Total Equitable Choosability of Graphs, (with J. Mudrock^, M. Pelsmajer), Graphs and Combinatorics, 34 (2019), 16371649.
summary:
An equitable coloring is a proper coloring of a graph such that the sizes of the color classes differ by at most one. In 1994, Fu conjectured that for any simple graph G, the total graph of G, T(G), is equitably kcolorable whenever k ≥ max{χ(T(G)), D+2}, where χ(T(G)) is the chromatic number of the total graph of G and D is the maximum degree of G. Recall that vertex coloring of T(G) is the simultaneous proper coloring of vertices and edges of G.
We investigate the list coloring analogue, as introduced by Kostochka, Pelsmajer, and West (2003), which prescribes an upper bound on the size of each color class in the list coloring. A graph is equitably kchoosable if it has a proper list coloring whenever vertices have lists of size k, where each color is used on at most V(G)/k vertices. In the spirit of Fu's conjecture, we conjecture that for any simple graph G, T(G) is equitably kchoosable whenever k ≥ max{χ_{L}(T(G)), D+2} where χ_{L}(T(G)) is the list chromatic number of T(G).
We first prove sharp results on equitable choosability of all powers of paths and cycles, verifying the conjecture and more for these graphs. Our main result is the proof of this conjecture for all graphs satisfying D ≤ 2. Note that, it isn't enough to prove equitable kchoosability for every component of a graph. The disconnected case of the proof of our theorem requires development of new a list decomposition tool that should prove useful for other problems in equitable kchoosability of graphs. In fact, we prove equitable 4choosability for graphs where components may be square of any path, square of any cycle on at least 6 vertices, or a copy of K_{4}, and we also prove equitable 3choosability for graphs where each component is a square of a cycle of length divisible by 3 or a square of a path. So we find exactly which total graphs T(G) with D=2 are equitably 3choosable.
 Proportional Choosability: a new list analogue of equitable coloring, (with J. Mudrock^, M. Pelsmajer, R. Reiniger), Discrete Mathematics, 342 (2019), 23712383.
summary:
In 2003, Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability which prescribes an upper bound on the size of each color class in the list coloring (unlike equitable coloring which prescribes both an upper and lower bound on the sizes of the color classes). In this paper, we motivate and define a new list analogue of equitable coloring called proportional choosability. For each color c in an list assignment L of a graph, let n(c), multiplicity of c, be the number of vertices v whose list L(v) contains c. Given a klistassignment L of a graph G, proportional Lcoloring of G is a proper Lcoloring in which each color c is used either ceiling or floor of n(c)/k times. Note that this gives exactly the definition of equitable coloring when the same list of size k is assigned to all vertices. A graph G is proportionally kchoosable if a proportional Lcoloring of G exists whenever L is a kassignment for G.
We use matching theory to show that proportional choosability is monotonic in k, meaning that if G is proportionally kchoosable, then it must be proportionally (k+1)choosable as well. We also show that proportional kchoosability is monotone, meaning that if H is a subgraph of G and G is proportionally kchoosable, then H is also proportionally kchoosable. These results are surprising, considering that equitable coloring and equitable list coloring do not have these nice properties. We give an algorithmic argument to convert an equitable Lcoloring with some additional restrictions into a proportional Lcoloring for a kassignment L of G with every color having multiplicity less than 2k, which helps us prove that any graph G is proportionally kchoosable whenever k ≥ D(G) + V(G)/2, where D(G) is the max degree of G. We use matching theory to completely characterize the proportional choosability of stars and the disjoint union of cliques. Note that handling disconnected graphs is still a challenge, just like in equitable choosability.
 On AlonTarsi Number and Chromaticchoosability of Cartesian Products of Graphs, (with J. Mudrock^), The Elect. Journal of Combinatorics, 26 (2019), article P1.3.
summary:
We study the list chromatic number of Cartesian products of graphs through the AlonTarsi number as defined by Jensen and Toft (1995) in their seminal book on graph coloring problems. The AlonTarsi number of G, AT(G), is the smallest k for which there is an orientation, D, of G with max indegree k1 such that the number of even and odd circulations contained in D are different. It is known that χ(G) ≤ χ_{L}(G) ≤ χ_{P}(G) ≤ AT(G), where χ(G) is the chromatic number, χ_{L}(G) is the list chromatic number, and χ_{P}(G) is the paint number of G. In this paper we find families of graphs G and H such that χ(G□H) = AT(G□H), reducing this sequence of inequalities to equality. Here G□H denotes the Cartesian product of the graphs G and H.
We show that the AlonTarsi number of the Cartesian product of an odd cycle and a path is always equal to 3 (this proof is featured in two forthcoming textbooks on Combinatorial Nullstellensatz and on Graph Coloring Methods). This result is then extended to show that if G is an odd cycle or a complete graph and H is a graph on at least two vertices containing the Hamilton path w1, w2, ...., wn such that for each i, wi has a most k neighbors among the vertices preceding it, then AT(G□H) ≤ D(G)+k, where D(G) is the maximum degree of G. We discuss other extensions for G□H, where G is such that V(G) can be partitioned into odd cycles and complete graphs, and H is a graph containing a Hamiltonian path. We apply these bounds to get chromaticchoosable Cartesian products, e.g. when G is the join of a clique and an odd cycle and H is a path, in fact we show that these families of graphs have χ(G) = AT(G), improving previously known bounds.
 On Graph FallColoring  Existence and Constructions, (with C. Mitillos^), Graphs and Combinatorics, 35 (2019), 16331646.
summary:
Graph FallColoring, also known as Idomatic Partition or Independent Domatic Partition of graphs, was formally introduced by Dunbar, Hedetniemi, Hedetniemi, Jacobs, Knisely, Laskar and Rall in 2000 as an extension of both Graph Coloring and Graph Domination. It asks for a partition of the vertex set of a given graph into independent dominating sets, or equivalently into maximal independent sets. We study two fundamental questions related to this concept: when such a partition of vertices can exist, and how it relates to a proper coloring.
We construct graphs with a large number of possible Fallcolorings, and characterize their independent dominating sets. We use this construction to create graphs with arbitrarily large Fallsets (collection of k such that the graph has a fall coloring with k colors), whose elements have arbitrarily large gaps between them; in fact the Fallsets can be arbitrarily long arithmetic sequences with prescribed common difference. Furthermore, by extending our construction, we answer a question of Dunbar et al. (2000) by constructing a family of graphs with arbitrarily far apart chromatic number and fallchromatic number.
We give a lower bound on the minimum degree which ensures that every kcoloring of a given kcolorable graph is also a kfallcoloring. This can be thought of as an improvement of an old result of Bollobas (1978) on sufficient minimum degree for uniquely colorable graphs. Moreover, this result shows the existence of k disjoint independent dominating sets in a dense graph containing k disjoint independent sets; a result along the lines of a similar one by Erdos et al. (1982) for the existence of two disjoint independent dominating sets. We then prove the sharpness of this bound, by constructing a graph with lower minimum degree and no kfallcoloring. We also construct a family of graphs whose set of kcolorings, for all k, includes both nonfallcolorings and fallcolorings, illustrating the complex relation between fall and nonfall colorings of a graph even when both exist.
 Combinatorial Nullstellensatz and DPColoring of Graphs, (with J. Mudrock), Discrete Mathematics, Volume 343 (2020), article 112115.
summary:
We initiate the study of applying the Combinatorial Nullstellensatz to the DPcoloring of graphs even though, as is wellknown, the AlonTarsi theorem does not apply to DPcoloring. The key obstacle to overcome in applying the Combinatorial Nullstellensatz to DPcoloring is: the graph polynomial is typically viewed as a polynomial over the reals which allows us only to prove results in the DPcoloring context on covers that correspond to list assignments. Here we view graph polynomials as polynomials over some appropriate finite field which allows us to apply the Combinatorial Nullstellensatz to certain covers with list sizes bounded by a power of a prime. This flexibility allows us to apply the Combinatorial Nullstellensatz, and the tools derived from it, to many covers that do not correspond to any list assignment and to coloring problems of Slabelings (a farreaching generalization of many coloring problems such as signed colorings, DPcoloring, group coloring, and coloring of gained graphs).
We define the notion of good covers of prime order which allows us to apply the Combinatorial Nullstellensatz to DPcoloring.
We apply these new tools along with the Quantitative Combinatorial Nullstellensatz to DPcoloring of the cones of certain bipartite graphs and uniquely 3colorable graphs. We also extend a result of Akbari, Mirrokni, and Sadjad (2006) on unique list colorability to the context of DPcoloring. We establish a sufficient algebraic condition for a graph G to be 3DPcolorable, and for a connected graph G with cycles, we reduce the number of polynomials to be tested to at most 2^(E(G)V(G)+1). Finally, we completely determine the DPchromatic number of the squares of all cycles.
 A Simple Characterization of Proportionally 2Choosable Graphs, (with J. Mudrock^, M. Pelsmajer, R. Reiniger), Graphs and Combinatorics, 36 (2020), 679687.
summary:
We recently introduced proportional choosability, a new list analogue of equitable coloring. Like equitable coloring, and unlike list equitable coloring (a.k.a. equitable choosability), proportional choosability bounds sizes of color classes both from above and from below. See the definitions in the previous paper's summary above. Here we show that a graph is proportionally 2choosable if and only if it is a linear forest such that its largest component has at most five vertices and all of its other components have two or fewer vertices. We also construct counterexamples that show that characterizing equitably 2choosable graphs is still open. Some intriguing questions about proportional choosability of paths are proposed.
 A Note on the Chromatic Number of the Square of Kneser Graph K(2k+1,k), (with JH. Kang), Discrete Mathematics, 343 (2020), article 111630.
summary:
Kneser graphs have been wellstudied for their rich structural and extremal properties, especially with regard to coloring problems since at least 1955 when M. Kneser formulated the problem of finding the chromatic number of what came to be called the Kneser graph. This problem was famously solved by Lovasz (and independently by Barany) in 1978 using topological methods. The vertices of Kneser graph K(n,k) are the subsets of [n] of cardinality k, two vertices are adjacent if and only if they are disjoint. The square G^{2} of a graph G is defined on the vertex set of G with two vertices adjacent if their distance in G is at most 2.
Zoltan Furedi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first nontrivial problem arises when n=2k+1, that is the Odd graph. This remains an open problem and it is believed that the chromatic number χ(K^{2}(2k+1,k)) = 2k+c where c is a constant. The best known upper bounds are by Kim and Park: (8k/3) + (20/3) for k ≥ 3 (2014) and (32k/15) + 32 for k ≥ 7 (2016). Kim and Park conjecture that χ(K^{2}(2k+1,k)) ≤ 2k + 2 for all k large enough.
We employ graph homomorphisms, Cartesian products of graphs, and linear congruences integrated with combinatorial arguments to prove an upper bound: 2(k+1) + 2log_{2}(k) for k ≥ 3, which matches the conjectured leading term of 2k. This is the best known upper bound till date. We also show that the conjecture is true, with a bound of 2k+2, for all k such that k+1 is a power of 2.
 Criticality, The List Color Function, and List Coloring the Cartesian Product of Graphs, (with J. Mudrock^), Journal of Combinatorics, Volume 12 (2021), 479514.
summary:
We introduce a notion of colorcriticality in the context of chromaticchoosability, χ_{L}(G)=χ(G), whereχ(G) is the chromatic number and χ_{L}(G) is the list chromatic number of G. We define a graph G to be strong kchromaticchoosable if χ(G)=k and every (k1)listassignment for which G is not listcolorable has the property that the lists are the same for all vertices. That is the usual coloring is, in some sense, the obstacle to better listcoloring. We prove basic properties of strongly chromaticchoosable graphs such as chromaticchoosability and vertexcriticality, and we construct infinite families of strongly chromaticchoosable graphs including cliques, odd cycles, and many more.
Using results on unique list colorability based on Combinatorial Nullstellensatz, we derive a sufficient condition for the existence of at least two list colorings of strongly chromaticchoosable graphs and use it to show that: if M is a strong kchromaticchoosable graph with E(M) at most V(M)(k2) and H is a graph that contains a Hamilton path, w1, w2, ...., wn, such that for each i, wi has a most r neighbors among the vertices preceding it, then χ_{L}(M□H) ≤ k + r  1. This shows chromatic choosability for every M when H is a path (giving sharpness of the bound for r=1). We show that this bound is sharp for all r ≥ 1 by generalizing the theorem to apply to H that are (M,r)Cartesian accommodating. This is a notion we define with the help of the list color function, P_{L}(G,k), the list analogue of the chromatic polynomial, that counts the number of different list colorings guaranteed for G with every klistassignment. The sharpness examples are constructed recursively as: S(M,B',r) that glues together P_{L}(M,k+r2) disjoint copies of S(M,B',r1), starting with S(M,B',1)=B', a subdivision of a star with P_{L}(M,k)1 leaves. This gives us recursive constructions of large chromaticchoosable graphs.
We use the list color function to determine the list chromatic number of certain starlike graphs, here K_{(1,s)} is the star with s leaves: χ_{L}(M□K_{(1,s)}) = k if s < P_{L}(M,k), or k+1 if s ≥ P_{L}(M,k), where M is any strong kchromaticchoosable graph. We use the results that P_{L}(M,k)=P(M,k) when M is an odd cycle (C_{(2l+1)}), complete graph (K_{n}), or the join of an odd cycle with a complete graph to prove:
χ_{L}(C_{(2l+1)}□K_{(1,s)}) transitions from 3 (its chromatic number) to 4 at exactly s= 2^{(2l+1)}2; χ_{L}(K_{n}□K_{(1,s)}) transitions from n (its chromatic number) to n+1 exactly at s= n!; and χ_{L}((K_{n}∨C_{(2l+1)}□K_{(1,s)}) transitions from n+3 (its chromatic number) to n+4 at s=(1/3) (n+3)! (4^{l}1). We can extend this result to get chromatic choosability when the second factor is a subdivision of a star or an appropriately bounded rooted tree.
 List Coloring a Cartesian Product with a Complete Bipartite Factor, (with J. Mudrock), Graphs and Combinatorics, 35 (2019), 15711583.
summary:
This paper is a continuation of the paper above "Criticality, The List Color Function, and List Coloring the Cartesian Product of Graphs".
We study χ_{L}(G□K_{(a,b)}), the list chromatic number of the Cartesian product of any graph G on n vertices, and a complete bipartite graph with partite sets of size a and b. We have two motivations. A classic result on the gap between list chromatic number and the chromatic number tells us χ_{L}(K_{(a,b)}) = 1 + a if and only if b ≥ a^a. Since χ_{L}(K_{(a,b)}) ≤ 1 + a for any b, this result tells us the values of b for which χ_{L}(K_{(a,b)}) is as large as possible and far from its chromatic number χ(K_{(a,b)})=2. In this paper we seek to understand when χ_{L}(G□K_{(a,b)}) is far from χ(G□K_{(a,b)}) = max{χ(G), 2}. It is easy to show χ_{L}(G□K_{(a,b)}) ≤ χ_{L}(G)+a. Borowiecki et al. (2006) showed that this bound is attainable if b is sufficiently large; specifically, χ_{L}(G□K_{(a,b)}) = χ_{L}(G)+a whenever b ≥ (χ_{L}(G)+a1)^{(an)}.
Given any graph G and a, we wish to determine f(G,a), the smallest b such that χ_{L}(G□K_{(a,b)}) = χ_{L}(G)+a. In this paper we show that the list color function, P_{L}(G,k), the list analogue of the chromatic polynomial, that counts the number of different list colorings guaranteed for G with every klistassignment, provides the right concept and tool for making progress on this problem. We prove that for any graph G, χ_{L}(G□K_{(a,b)}) = χ_{L}(G)+a whenever b ≥ (P_{L}(G, χ_{L}(G)+a1))^{a}, a sharp bound that is a vast improvement on the previous results.
The argument can be generalized to give us conditions when χ_{L}(G□H) is guaranteed to be far from χ(G□H) for any bipartite graph H. Let H be a bipartite graph with partite sets A and B where A=a and B=b. Let d = min degree of vertices in B. If b ≥ (P_{L}(G, χ_{L}(G)+d1))^a, then χ_{L}(G□H) ≥ χ_{L}(G)+d.
We show these bounds are sharp: if M is a strong kchromatic choosable graph and k ≥ a+1, then χ_{L}(M□ K_{(a,b)}) = χ_{L}(G)+a if and only if b ≥ (P_{L}(M, χ_{L}(M)+a1))^{a}. This is a generalization of results in the previous paper, see the summary above. This can be applied to get explicit bounds, e.g. f(C_{(2l+1)},2) = (P_{L}(C_{(2l+1)},4))^{2} = 9(9^{l}1)^{2}; and f(K_{n},a)= (P_{L}(K_{n}, n+a1))^{a} = ((n+a1)!/(a1)!)^{a}. We also prove a general lower bound on f(G,a) for strongly chromaticchoosable graphs.
 Partial DPColoring of Graphs, (with J. Mudrock, M. Pelsmajer), Discrete Mathematics, 344 (2021), article 112306.
summary:
In 1980 Albertson and Berman introduced partial coloring, and then in 2000, Albertson, Grossman, and Haas introduced partial list coloring. Here we initiate the study of partial coloring for DPcoloring (aka, correspondence coloring), a generalization of list coloring introduced by Dvorak and Postle in 2015, that has been studied extensively since then. Intuitively, DPcoloring considers the worstcase scenario of how many colors we have to use in a list coloring if we no longer can identify the names of the colors. The partial tchromatic number of a graph G, denoted A(G,t), is the maximum number of vertices in G that can be colored with t colors. Clearly, A(G,t) ≥ tn/χ(G) for each t in {1, ...., χ(G)}, where χ(G) is the chromatic number of the n vertex graph G. The list coloring version of this concept is the partial tchoice number of a graph G, denoted A_{L}(G,t), the maximum number of vertices that can be properly colored for each tlistassignment. The Partial List Coloring Conjecture, that is still open, states that for any graph G, A_{L}(G,t) ≥ tn/χ_{L}(G) for each t in {1, ...., χ_{L}(G)}, where χ_{L}(G) is the list chromatic number of G. It is now natural to define the partial DP tchromatic number, A_{DP}(G,t), and extend this conjecture to DPcoloring.
We show that while the DPcoloring analogue of the Partial List Coloring Conjecture does not hold, several results on partial list coloring can be extended to the DPcoloring context. We call a graph partially DPnice if it satisfies A_{DP}(G,t) ≥ tn/χ_{DP}(G) for each t in {1, ...., χ_{DP}(G)}, where χ_{DP}(G) is the DPchromatic number of G. We develop a new characterization of 2fold covers and use it to construct several examples of graphs G with χ_{DP}(G)=3 and A_{DP}(G,2) less than 2n/3, including an infinite family of graphs on 5k vertices, and the cube graph Q_{3}. We show that the Wagner graph V_{8} is partially DPnice, A_{DP}(V_{8},2)=6, and that V_{8} has no induced subgraph with DPchromatic number 2 and order at least (2/3)V(V_{8}) which answers a natural open question about partial DP tchromatic number of induced subgraphs.
We can conclude that every connected, subcubic, trianglefree graph, with the unique exception of Q_{3}, is partially DPnice. We use feedback vertex covers to observe that any nontrivial planar graph of girth at least 5 is partially DPnice. We prove several more classes of graphs are partially DPnice, including chordal graphs and seriesparallel graphs. We also consider the join of a graph with a complete graph and prove that: for any graph G, there exists a p such that G∨K_{p} is partially DPnice.
We prove that A_{DP}(G,t) ≥ n/ceiling[χ_{DP}(G)/t] for each t in {1, ...., χ_{DP}(G)}. It follows that for any graph G, the inequality A_{DP}(G,t) ≥ tn/χ_{DP}(G) holds true for at least half of the values of t. The main tool here is a subadditivity lemma: for any graph G and t1, ...., tk, A_{DP}(G,t)) ≤ ∑_{i=1 to k}(A_{DP}(G,ti)) where t = ∑_{i=1 to k}(ti).
 On Equitable List Arboricity of Graphs, (with J. Mudrock, M. Pelsmajer), The Australasian Journal of Combinatorics, 80 (2021), 419441.
summary:
Equitable list arboricity, introduced by Zhang in 2016, generalizes the notion of equitable list coloring by requiring each color class to be acyclic (instead of an independent set), in addition to the usual upper bound on the size of each color class. G is equitably klist arborable if an equitable, arborable list coloring of G exists for every list assignment for G that associates with each vertex in G a list of k available colors.
Zhang conjectured that any graph G is equitably klist arborable for each k satisfying k ≥ ceiling[(1+D(G))/2], where D(G) is the maximum degree of G. We verify this conjecture for powers of cycles by applying a new lemma, a general tool for recognizing a set S of vertices in a graph G and its list coloring that would allow an extension of an equitable, arborable list coloring of GS to an equitable, arborable list coloring of G. This tool is also applied to give improved colorings for powers of a path.
We also propose a stronger version of Zhang's Conjecture for certain connected graphs: any connected graph G is equitably klist arborable for each k satisfying k ≥ ceiling[D(G)/2] provided G is neither a cycle nor a complete graph of odd order. We verify this stronger version of Zhang's Conjecture for powers of paths, 2degenerate graphs, and certain other graphs.
We use probabilistic and algorithmic arguments to show that if G is equitably klist arborable it does not necessarily follow that G is equitably (k+1)list arborable which addresses a question of DrgasBurchardt et al. (2018). We also show that it is not necessary that if a graph G is equitably klist arborable then G is also equitably vertex karborable.
 Equitable Choosability of Disjoint Unions of Stars, (with J. Mudrock, T. Wagstrom^), Graphs and Combinatorics, 38 (2022), article 163.
summary:
Equitable kchoosability is a list analogue of equitable kcoloring introduced by Kostochka, Pelsmajer, and West in 2003, which prescribes an appropriate upper bound on the size of each color class in the list coloring. See the definitions in the paper summaries above. It is known that if vertex disjoint graphs G and H are equitably kchoosable, the disjoint union of G and H may not be equitably kchoosable. Also, unlike many other variants of list coloring problems, a complete characterization of equitably 2choosable graphs is not known, and in general not much is known about equitable kchoosability for small k. Here, we study these problems under the equitable choosability of the disjoint union of stars.
Perhaps surprisingly, since most coloring problems with 2 colors or on stars tend to be easy, we show that determining whether the disjoint union of n stars is equitably choosable is NPcomplete when the same list of two colors is assigned to every vertex. We completely determine when the disjoint union of 2 arbitrary stars is equitably 2choosable. This makes progress on the task of identifying which graphs are equitably 2choosable, and also shows that there are only 14 equitably 2choosable graphs (up to isomorphism) that are the disjoint union of two stars, unlike the infinitely many equitably 2colorable graphs that are the disjoint union of two stars. We completely determine when the disjoint union of n identical stars is equitably 2choosable, with the answer surprisingly depending on the parity of n. We use an extremal choice of a partial list coloring that minimizes the difference of the cardinalities of the sets of uncolored vertices in the two stars, along with a greedy partial list coloring process, to prove a sharp sufficient condition for the equitable kchoosability of two stars for arbitrary k.
 A Generalization of the Graph Packing Theorems of SauerSpencer and Brandt, (with B. Reiniger), Combinatorica, 42 (2022), 1347–1356.
summary:
We prove a common generalization of the celebrated SauerSpencer packing theorem and a theorem of Brandt concerning finding a copy of a tree inside a graph: Let G be a graph of maximum degree D, and H a cdegenerate graph, both on n vertices, with degree sequences (g_{1}, ..., g_{n}) and (h_{1}, ..., h_{n}) in nonincreasing order, respectively. If ∑_{i=1 to D}(h_{i}) + ∑_{i=1 to c}(g_{i}) < n then G and H pack.
This proof leads to the characterization of the extremal graphs in the case of Brandt's theorem: If G is a graph of maximum degree D, and F is a forest, both on n vertices, and 3D+l*(F) ≤ n, then G and F pack, unless n is even, G is a perfect matching, and F is a star with (n1) leaves; where l*(F), number of "excess" leaves, is the difference between the number of leaves and twice the number of nontrivial components of F.
 DPColoring of Cartesian Product of Graphs, (with J. Mudrock, G. Sharma^, Q. Stratton^), Journal of Graph Theory, Volume 103, 2023, 285306.
summary:
DPcoloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvorak and Postle in 2015, that has been studied extensively since then. Intuitively, DPcoloring considers the worstcase scenario of how many colors we have to use in a list coloring if we no longer can identify the names of the colors. Motivated by known results related to list coloring Cartesian products of graphs, we initiate the study of the DPchromatic number of the Cartesian product of any two graphs G and H, denoted by χ_{DP}(G□H). With a simple generalization of list coloring arguments we show that χ_{DP}(G□H) = min{χ_{DP}(G) + col(H), χ_{DP}(H) + col(G)}  1 where col(H) is the coloring number of the graph H.
Most of the paper is focussed on studying the problems arising out of showing the sharpness for this bound, and building tools for lower bounds on the DPchromatic number for this. First, we define the notion of volatile coloring which gives a characterization of the bad covers of the Cartesian product of two graphs with a complete bipartite factor. This is applied to show a large class of sharpness for the basic upper bound above: for any graph G, χ_{DP}(G□K_{(a,b)}) = χ_{DP}(G)+a whenever b ≥ (P_{DP}(G, χ_{DP}(G)+a1))^{a}. Recall that P_{DP}(G,m) is the DP color function of a graph G, DP coloring analogue of the chromatic polynomial, which counts the minimum number of DPcolorings over all possible mfold covers. See our other papers for results on the DP color function.
Building upon this result, in the rest of the paper, we will show evidence that the DP color function is a useful tool in the study of the DPchromatic number of the Cartesian product of graphs. Considering the sharpness of Theorem 4, also inspires us to consider a more general question: given a graph G and a, we wish to determine f(G,a), the smallest b such that χ_{DP}(G□K_{(a,b)}) = χ_{L}(G)+a.
Next, we define canonical labeling and twistedcanonical labeling of covers which give a characterization of the bad covers of odd and even cycles respectively. Using these tools along with volatile coloring, we showing that sharpness Theorem itself is also sharp when G is an even cycle and k = 1; that is, for any m, f(C_{2m+2}, 1) = P_{DP}(C_{2m+2}, 3) = 2^{2m+2}  1.
Finally, we improve the sharpness Theorem when G is a cycle. Using the tools we have described so far, we construct random covers using a combination of random matchings defined using an equivalence relation on an appropriate set of colorings, and matchings defined using canonical and twistedcanonical labelings. We show that there exists an appropriate bad cover by counting the expected number of volatile colorings and applying the bound on volatile colorings for good covers. This improved theorem gives better bounds on f(C_{m}, k) of the form
c_{k} (P_{DP}(C_{m}, k+2) / (k+2))^{k} where the form of c_{k} depends on the parity of the cycle. In particular we get that for any m, f(C_{2m+1}, 1) = P_{DP}(C_{2m+1}, 3)/3 = (2^{2m+1}  2)/3.
 A Note on Fractional DPColoring of Graphs, (with D. Dominik^, J.Mudrock), Discrete Mathematics 347 (2024), article 114123.
summary:
Details forthcoming.
In the meantime, checkout Section 1.3 of the paper.
 Flexible list colorings: Maximizing the number of requests satisfied, (with R. Mathew, J. Mudrock, M. Pelsmajer), Journal of Graph Theory, 106 (2024), 887906.
summary:
Details forthcoming.
In the meantime, checkout Section 1 of the paper.
 DPcoloring of graphs from random covers, (with A. Bernshteyn, D. Dominik^, J.Mudrock), Random Structures \& Algorithms, under revision.
summary:
Details forthcoming.
In the meantime, checkout Sections 1.3 and 1.4 of the paper.
 On strongly and robustly critical graphs, (with A. Bernshteyn, J.Mudrock, G. Sharma^), submitted for publication.
summary:
Details forthcoming.
In the meantime, checkout Sections 1 of the paper for a detailed overview.

Papers on Enumerative Graph Theory:
 Criticality, The List Color Function, and List Coloring the Cartesian Product of Graphs, (with J. Mudrock^), Journal of Combinatorics, Volume 12 (2021), 479514.
summary:
We introduce a notion of colorcriticality in the context of chromaticchoosability, χ_{L}(G)=χ(G), whereχ(G) is the chromatic number and χ_{L}(G) is the list chromatic number of G. We define a graph G to be strong kchromaticchoosable if χ(G)=k and every (k1)listassignment for which G is not listcolorable has the property that the lists are the same for all vertices. That is the usual coloring is, in some sense, the obstacle to better listcoloring. We prove basic properties of strongly chromaticchoosable graphs such as chromaticchoosability and vertexcriticality, and we construct infinite families of strongly chromaticchoosable graphs including cliques, odd cycles, and many more.
Using results on unique list colorability based on Combinatorial Nullstellensatz, we derive a sufficient condition for the existence of at least two list colorings of strongly chromaticchoosable graphs and use it to show that: if M is a strong kchromaticchoosable graph with E(M) at most V(M)(k2) and H is a graph that contains a Hamilton path, w1, w2, ...., wn, such that for each i, wi has a most r neighbors among the vertices preceding it, then χ_{L}(M□H) ≤ k + r  1. This shows chromatic choosability for every M when H is a path (giving sharpness of the bound for r=1). We show that this bound is sharp for all r ≥ 1 by generalizing the theorem to apply to H that are (M,r)Cartesian accommodating. This is a notion we define with the help of the list color function, P_{L}(G,k), the list analogue of the chromatic polynomial, that counts the number of different list colorings guaranteed for G with every klistassignment. The sharpness examples are constructed recursively as: S(M,B',r) that glues together P_{L}(M,k+r2) disjoint copies of S(M,B',r1), starting with S(M,B',1)=B', a subdivision of a star with P_{L}(M,k)1 leaves. This gives us recursive constructions of large chromaticchoosable graphs.
We use the list color function to determine the list chromatic number of certain starlike graphs, here K_{(1,s)} is the star with s leaves: χ_{L}(M□K_{(1,s)}) = k if s < P_{L}(M,k), or k+1 if s ≥ P_{L}(M,k), where M is any strong kchromaticchoosable graph. We use the results that P_{L}(M,k)=P(M,k) when M is an odd cycle (C_{(2l+1)}), complete graph (K_{n}), or the join of an odd cycle with a complete graph to prove:
χ_{L}(C_{(2l+1)}□K_{(1,s)}) transitions from 3 (its chromatic number) to 4 at exactly s= 2^{(2l+1)}2; χ_{L}(K_{n}□K_{(1,s)}) transitions from n (its chromatic number) to n+1 exactly at s= n!; and χ_{L}((K_{n}∨C_{(2l+1)}□K_{(1,s)}) transitions from n+3 (its chromatic number) to n+4 at s=(1/3) (n+3)! (4^{l}1). We can extend this result to get chromatic choosability when the second factor is a subdivision of a star or an appropriately bounded rooted tree.
 On the Chromatic Polynomial and Counting DPColorings of Graphs, (with J. Mudrock), Advances in Applied Mathematics, Volume 123 (2021), article 102131.
summary:
The chromatic polynomial of a graph G, P(G,m), counts the number of proper mcolorings of G. It was introduced by Birkhoff in 1912 to study the fourcolor problem, and is one the central objects in algebraic graph theory. The list color function of graph G, P_{L}(G,m), is a list coloring analogue of the chromatic polynomial that has been studied since before 1992, primarily through comparisons with the corresponding chromatic polynomial. DPcoloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvorak and Postle in 2015, that has been studied extensively since then. Intuitively, DPcoloring considers the worstcase scenario of how many colors we have to use in a list coloring if we no longer can identify the names of the colors.
In this paper, we introduce a DPcoloring analogue of the chromatic polynomial called the DP color function, denoted P_{DP}(G,m), and ask several fundamental open questions about it, making progress on some of them. Motivated by known results related to the list color function, we show that while the DP color function behaves similar to the list color function for some graphs, there are also some surprising differences.
A central result on the list color function states that P_{L}(G,m)=P(G,m) whenever m is large enough, but we will show that for any g ≥ 3 there exists a graph, G, with girth g such that P_{DP}(G,m) < P(G,m) when m is sufficiently large. We also study the asymptotics of P(G,m)  P_{DP}(G,m) for a fixed graph G.
We use probabilistic arguments to prove a sharp lower bound on P_{DP}(G,m) which is the same as the lower bound on P(G,m) when G is bipartite, as claimed by the famous Sidorenko's conjecture on counting homomorphisms from a bipartite graph. This bound along with our other results allow us to show that a natural analogue of Sidorenko's conjecture for the DP color function holds only for trees.
We develop techniques to compute P_{DP}(G,m) exactly and apply them to certain classes of graphs such as chordal graphs (where P_{DP}(G,m)=P(G,m)), unicyclic graphs (where the answer depends on the parity of its girth), and cycles with a chord (where the answer depends on the parities of the lengths of the two maximal cycles properly contained in such a graph). Finally, we make progress towards showing that for any graph G, there is a p such that P_{DP}(G∨K_{p}, m) = P(G∨K_{p}, m) for large enough m.
 The DP Color Function of Joins and VertexGluings of Graphs, (with J. Becker^, J. Hewitt^, M. Maxfield^, J. Mudrock, D. Spivey^, S. Thomason^, T. Wagstrom^), Discrete Mathematics, 345 (2022), article 113093.
summary:
DPcoloring (also called correspondence coloring) is a generalization of list coloring that has been widely studied in recent years after its introduction by Dvorak and Postle in 2015. As the analogue of the chromatic polynomial P(G,m), the DP color function of a graph G, denoted P_{DP}(G,m), counts the minimum number of DPcolorings over all possible mfold covers. Chromatic polynomials for joins and vertexgluings of graphs are well understood and widely used to build the chromatic polynomials of graphs built through a sequence of such operations, but the effect of these graph operations on the DP color function is not known.
In this paper we make progress on understanding the DP color function of the join of a graph with a complete graph and vertexgluings of certain graphs. We also develop tools to study the DP color function under these graph operations, such as: given vertex disjoint graphs G_{1}, .... G_{n}, we define amalgamated cover, a natural analogue of "gluing" mfold covers of each G_{i} together so that we get an mfold cover for any G formed by vertex gluing the graphs G_{1}, .... G_{n}; and we define separated covers, a natural analogue of "splitting" an mfold cover of any G formed by cliquegluing the graphs G_{1}, .... G_{n} into separate mfold covers for each G_i. And we study the threshold (smallest m) beyond which the DP color function of a graph constructed with these operations equals its chromatic polynomial.
 Nonchromaticadherence of the DP Color Function via Generalized Theta Graphs, (with Manh Vu Bui^, M. Maxfield^, J. Mudrock, Paul Shin^, S. Thomason^), Graphs and Combinatorics Volume 39, 2023, article number 42.
summary:
DPcoloring (also called correspondence coloring) is a generalization of list coloring that has been widely studied in recent years after its introduction by Dvorak and Postle in 2015. The chromatic polynomial of a graph is an extensively studied notion in combinatorics since its introduction by Birkhoff in 1912; denoted P(G,m), it equals the number of proper mcolorings of graph G. Counting function analogues of the chromatic polynomial have been introduced and studied for list colorings: P_{L}, the list color function (1990); DP colorings: P_{DP}, the DP color function (2019), and P_{DP}^{*}, the dual DP color function (2021). For any graph G and m, P_{DP}(G, m) ≤ P_{L}(G,m) ≤ P(G,m) ≤ P_{DP}^{*}(G,m).
A fundamental open question on the list color function asks whether the list color function of a graph and the corresponding chromatic polynomial stay the same after the first point at which they are both nonzero and equal. A function f is chromaticadherent if for every graph G, f(G,a) = P(G,a) for some a ≥ χ(G) implies that f(G,m) = P(G,m) for all m ≥ a. It is not known if the list color function and the DP color function are chromaticadherent. We show that the DP color function is not chromaticadherent by studying the DP color function of Generalized Theta graphs. The tools we develop along with the Rearrangement Inequality give a new method for determining the DP color function of all Theta graphs and the dual DP color function of all Generalized Theta graphs.
 Bounding the List Color Function Threshold from Above, (with A. Kumar^, A. Liu^, J. Mudrock, P. Rewers^, P. Shin^, M.S. Tanahara^, K. To^), Involve: A journal of mathematics, Volume 16, 2023, 849–882.
summary:
In 1912 Birkhoff introduced the notion of the chromatic polynomial P(G,m), which counts the number of proper colorings with m colors in a graph G. The notion of chromatic polynomial was extended to list coloring in the early 1990s by Kostochka and Sidorenko. The list color function, P_{L}(G,m), the list analogue of the chromatic polynomial, that counts the number of different list colorings guaranteed for G with every mlistassignment. It follows that P_{L}(G,m) ≤ P(G,m). In general, the list color function can differ significantly from the chromatic polynomial for small values of m. In 1992, Donner showed that for any graph G there is a k such that P_{L}(G,m) = P(G,m) whenever m ≥ k. The list color function threshold of G, denoted t(G) is the smallest k ≥ χ(G) such that P_{L}(G,m) = P(G,m) whenever m ≥ k.
In 2009, Thomassen showed that for any graph G, t(G) ≤ V(G)^{10} + 1. Then, in 2017, Wang, Qian, and Yan significantly improved it to t(G) ≤ (1.14) E(G).
In an earlier work, it was proved that there is a positive constant c such that for each l ≥ 16, t(K_{2,n}) ≥ c sqrt(n), and it was conjectured that this lower bound captures the behavior of t(K_{2,n}).
In this paper we develop tools for bounding the list color function threshold of complete bipartite graphs from above. We show that for any n, t(K_{2,n}) ≤ (n + 2.05)/1.24. Interestingly, our proof makes use of classical results from Analysis such as Rolle’s Theorem and Descartes’ Rule of Signs. We also ask questions and prove some results regarding enumerativechromatic choosability of K_{2,n}.
 On Polynomial Representations of the DP Color Function: Theta Graphs and Their Generalizations, (with C. Halberg^, A. Liu^, J. Mudrock, P. Shin^, S. Thomason^), Journal of Combinatorics, 15 (2024), 451478.
summary:
The chromatic polynomial of a graph G, P(G,m), counts the number of proper mcolorings of G. It was introduced by Birkhoff in 1912 to study the fourcolor problem, and is one the central objects in algebraic graph theory. The list color function of graph G, P_{L}(G,m), is a list coloring analogue of the chromatic polynomial that has been studied since before 1992, primarily through comparisons with the corresponding chromatic polynomial. DPcoloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvorak and Postle in 2015, that has been studied extensively since then. Intuitively, DPcoloring considers the worstcase scenario of how many colors we have to use in a list coloring if we no longer can identify the names of the colors.
As the analogue of the chromatic polynomial P(G,m), the DP color function of a graph G, denoted P_{DP}(G,m), counts the minimum number of DPcolorings over all possible mfold covers. It is known that from our previous work, unlike the list color function P_{L}(G,m), for any g ≥ 3 there exists a graph, G, with girth g such that P_{DP}(G,m) < P(G,m) when m is sufficiently large. Thus, two fundamental open questions regarding the DP color function are: (i) for which G does there exist an N such that P_{DP}(G,m) = P(G,m) whenever m > N, (ii) given a graph G does there always exist an N and a polynomial p(m) such that P_{DP}(G,m) = p(m) whenever m > N?
Generalized Theta graphs, which have been widely studied for many graph theoretic problems, are the main subject of two classical papers on the chromatic polynomial which include the celebrated result that the zeros of the chromatic polynomials of the Generalized Theta graphs are dense in the whole complex plane with the possible exception of the unit disc around the origin (by including the join of Generalized Theta graphs with an edge this extends to all of the complex plane). It is natural to study the DP color function of these graphs, independent of our motivating questions.
In this paper we give exact formulas for the DP color function of a Theta graph based on the parity of its path lengths. This gives an explicit answer, including the formulas for the polynomials that are not the chromatic polynomial, to both the questions above for Theta graphs. This result illustrates the complex relationship that the DP color function has with the structure of odd and even cycles in a graph. From previous work, we know that girth being even forces P_{DP}(G,m) < P(G,m) when m is sufficiently large, but this result shows girth being odd can lead to complicated behavior. Despite this, in each of the four parity based cases we see that P_{DP}(G,m) equals a polynomial.
We extend this result to Generalized Theta graphs by characterizing the exact parity condition that ensures the DP color function eventually equals the chromatic polynomial. To answer the second question for Generalized Theta graphs, we confirm it for the larger class of graphs with a feedback vertex set of size one. Even though we do not have an explicit formula for the polynomial p(m) we know its three highest degree terms are the same as those of the corresponding chromatic polynomial. Our proof considers a decomposition of the graph G into a star G_{1} and a spanning forest G_{0}. The problem then reduces to carefully counting the number H_{0}colorings of G_{0} that are not Hcolorings of G, where H_{0} is the mfold cover of G_{0} induced by a given mfold H of G.
 On the List Color Function Threshold, (with A. Kumar^, J. Mudrock, P. Rewers^, P. Shin^, K. To^), Journal of Graph Theory, Vol 105, 2024, 386397.
summary:
In 1912 Birkhoff introduced the notion of the chromatic polynomial P(G,m), which counts the number of proper colorings with m colors in a graph G. The notion of chromatic polynomial was extended to list coloring in the early 1990s by Kostochka and Sidorenko. The list color function, P_{L}(G,m), the list analogue of the chromatic polynomial, that counts the number of different list colorings guaranteed for G with every mlistassignment. It follows that P_{L}(G,m) ≤ P(G,m). In general, the list color function can differ significantly from the chromatic polynomial for small values of m. In 1992, Donner showed that for any graph G there is a k such that P_{L}(G,m) = P(G,m) whenever m ≥ k. The list color function threshold of G, denoted t(G) is the smallest k ≥ χ(G) such that P_{L}(G,m) = P(G,m) whenever m ≥ k.
In 2009, Thomassen showed that for any graph G, t(G) ≤ V(G)^{10} + 1. Then, in 2017, Wang, Qian, and Yan significantly improved it to t(G) ≤ (1.14) E(G).
In 2009, Thomassen asked whether there a universal constant C such that for any graph G, t(G) ≤ χ_{L}(G) + C? We show that the answer to this question is no in a fairly strong sense by proving that there is a constant c such that for each l ≥ 16, t(K_{2,n})  χ_{L}(K_{2,n}) ≥ c sqrt(n). We conjecture that this lower bound captures the behavior of t(K_{2,n}).
In light of the bound of Wang, Qian, and Yan, Thomassen's Question, and our Theorem, it is natural to study the asymptotic behavior of the list color function threshold as the size of the graphs we consider tends toward infinity. We define the extremal functions d_{max}(m) = max {t(G)  χ_{L}(G) : G is a graph with at most m edges} and t_{max}(m) = max {t(G) : G is a graph with at most m edges}. By our Theorem and the bound of Wang, Qian, and Yan, we know that there exist constants such that c_{1} sqrt(m) ≤ d_{max}(m) ≤ c_{2} m for large enough m, and c_{3} sqrt(m) ≤ t_{max}(m) ≤c_{2} m for large enough m. We ask what is the asymptotic behavior of d_{max}(m) and t_{max}(m)? In particular, if t_{max}(m) grows faster than sqrt(m) then d_{max}(m) will be asymptotic to t_{max}(m).
 The DP Color Function of CliqueGluings of Graphs, (with M. Maxfield^, J. Mudrock, S. Thomason^), Enumerative Combinatorics and Applications, Volume 4, 2024, article S2R11.
summary:
DPcoloring (also called correspondence coloring) is a generalization of list coloring that has been widely studied in recent years after its introduction by Dvorak and Postle in 2015. As the analogue of the chromatic polynomial P(G,m), the DP color function of a graph G, denoted P_{DP}(G,m), counts the minimum number of DPcolorings over all possible mfold covers. Chromatic polynomials for cliquegluings of graphs, a fundamental graph operation used for characterizing many graph classes, are well understood and widely used to build the chromatic polynomials of graphs constructed through a sequence of such operations, but the effect of these graph operations on the DP color function is not known.
In this paper we study the DP color function of K_{p}gluings of graphs. Recently, Becker et. al. asked whether P_{DP}(G,m) ≤ (Π_{i=1 to n} P_{DP}(G_{i},m))( Π_{i=0 to p1} (mi) )^{n1} whenever m ≥ p, where the expression on the right is the DPcoloring analogue of the corresponding chromatic polynomial formula for a K_{p}gluing of G_{1}, ...., G_{n}. Don and Yang (2021) asked a simpler version of the same question as well. In a recent paper, we showed this inequality holds when p=1 (vertexgluings). In this paper we show this inequality holds for edgegluings (p=2). On the other hand, we show it does not hold for trianglegluings (p=3). These results also resolve the corresponding questions of Dong and Yang (2021). Finally, we show a relaxed version, based on a class of mfold covers that we conjecture would yield the fewest DPcolorings for a given graph, of the inequality holds when p ≥ 3.
 An Algebraic Approach for Counting DP3colorings of Sparse Graphs, (with S. Dahlberg and J. Mudrock), European Journal of Combinatorics, Volume 118, May 2024, 103890.
summary:
DPcoloring (or correspondence coloring) is a generalization of list coloring that has been widely studied since its introduction by Dvorák and Postle in 2015. As the analogue of the chromatic polynomial of a graph P(G,m), the DP color function of a graph G, denoted P_{DP}(G,m), counts the minimum number of DPcolorings over all possible mfold covers. A function f is chromaticadherent if for every graph G, f(G,a) = P(G,a) for some a ≥ χ(G) implies that f(G,m) = P(G,m) for all m ≥ a. It is known that the DP color function is not chromaticadherent, but there are only two known graphs that demonstrate this.
Suppose G is an nvertex multigraph and H is a 3fold cover of G, in this paper we associate with H a polynomial in n variables over the finite field of order 3, so that the number of nonzeros of this polynomial equals the number of Hcolorings of G. We then use a wellknown result of Alon and Furedi on the number of nonzeros of a polynomial to establish a nontrivial and sharp lower bound 3^{n  l/2} on P_{DP}(G,3) when 2n > l =E(G). As an immediate application, consider a nvertex planar graph G of girth at least 5. It is known that χ_{DP}(G) ≤ 3. Since number of edges in G is at most 5n/3, our bound implies P_{DP}(G,3) ≥ 3^{n/6}. This bound gives a major improvement on the previously known bounds of Thomassen (2007) and Postle and SmithRoberge (2022+) on both DPcolor function and the listcolor function of these graphs.
Finally, we use this bound to show that there are infinitely many graphs that demonstrate the nonchromaticadherence of the DP color function.
 A polynomial method for counting colorings of sparse graphs, (with S. Dahlberg and J. Mudrock), submitted for publication.
summary:
The coloring of planar graphs and its subfamilies has a long history starting with the four color problem in the nineteenth century. This history is intertwined with the related conjectures on existence of exponentially many such colorings (as a function of the number of vertices), going back at the least to Birkhoff’s work in 1930, and Birkhoff and Lewis’ enumerative extension of the four color conjecture in 1946 that for any nvertex planar graph G, the chromatic polynomial satisfies P(G, k) ≥ k(k1)(k2)(k3)^{(n3)} for all real numbers k ≥ 4. They proved this is true for k = 5, thus giving exponentially many 5colorings of planar graphs. After Thomassen in 1994 proved all planar graphs are 5choosable, there has been much work done on showing that planar graphs and their subfamilies have exponentially many list kcolorings for appropriate k in {3, 4, 5}. These proofs are typically intricate topological arguments specialized to the family of planar graphs under consideration.
In this paper, we give a unified and simple polynomial method for proving many such exponential lower bounds on the number of colorings
of sparse graphs without requiring any topological assumptions. Our results are set in the general framework of coloring Slabeled graphs, where S is a subset of a symmetric group, which includes classical and many other types of graph coloring as special cases. In fact, for each such choice of S there is a corresponding notion of coloring of a graph. The subset relation on the set of nonempty subsets of the symmetric group, induces a partial order on all these notions of coloring with the socalled DP coloring as the unique maximal element and the classical coloring as a minimal element. Our most general results will give exponential lower bounds on the enumerative functions of all these notions of coloring, as well as list coloring, for any appropriate sparse graph. Application of our lower bounds to families of planar graphs either improve previously known results or are the first such known results. For example, Signed graphs and their colorings have been widely studied since the 1980s but we do not know of any previous results on bounding the number of such colorings.
 Counting packings of listcolorings of graphs, (with J. Mudrock), Submitted for publication.
summary:
Given a list assignment for a graph, list packing asks for the existence of multiple pairwise disjoint list colorings of the graph. Several papers have recently appeared that study the existence of such a packing of list colorings. Formally, a proper Lpacking of a graph G of size k is a set of k pairwise disjoint proper Lcolorings of G where L is a list assignment of colors to the vertices of G. In this paper, we initiate the study of counting such packings of list colorings of a graph.
We define P_{l}^{*}(G,q,k) as the guaranteed number of proper Lpackings of G of size k over all list assignments L that assign q colors to each vertex of G, and we let P^{*}(G,q,k) be its classical coloring counterpart. We let P_{l}^{*}(G,q)= P_{l}^{*}(G,q,q) so that P_{l}^{*}(G,q) is the enumerative function for the previously studied list packing number. Note that the chromatic polynomial of G, P(G,q), is P^{*}(G,q,1), and the list color function of G, P_{l}(G,q), is P_{l}^{*}(G,q,1).
Inspired by the wellknown behavior of the list color function and the chromatic polynomial, we make progress towards the question of whether P_{l}^{*}(G,q,k) = P^{*}(G,q,k) when q is large enough. Our result generalizes the recent theorem of Dong and Zhang (2023), that improved results going back to Donner (1992) that answered a question of Kostochka and Sidorenko, about when the list color function equals the chromatic polynomial. Further, we use a polynomial method to generalize recently obtained bounds on the list packing number of sparse graphs like planar graphs and its subfamilies, to exponential lower bounds on the corresponding list packing functions.
 Counting listcolorings of unlabeled graphs, (with J. Mudrock), Submitted for publication.
summary:
The classic enumerative functions for counting colorings of a graph G, such as the chromatic polynomial P(G,k), do so under the assumption that the given graph is labeled. In 1985, Hanlon defined and studied the chromatic polynomial for an unlabeled graph G, P(G, k). Determining P(G, k) amounts to counting colorings under the action of automorphisms of G.
In this paper, we consider the problem of counting list colorings of unlabeled graphs. Unlike previous works, the challenge here is that Burnside's Lemma/ Orbit Counting Lemma is of limited utility in this context. List coloring of graphs is a widely studied generalization of classic coloring that was introduced by Vizing and by Erdos, Rubin, and Taylor in the 1970s. In 1990, Kostochka and Sidorenko introduced the list color function P_{l}(G, k) which is the guaranteed number of list colorings of a labeled graph G over all klist assignments of G. In this paper, we extend Hanlon's definition to the list context and define the unlabeled list color function P_{l}(G, k), of an unlabeled graph G.
In this context, we pursue a fundamental question whose analogues have driven much of the research on counting list colorings and its generalizations: For a given unlabeled graph G, does P_{l}(G, k) = P(G, k) when k is large enough? We show the answer to this question is yes for a large class of unlabeled graphs that include pointdetermining graphs (also known as irreducible graphs and as mating graphs). Pointdetermining graphs (also referred in literature as irreducible graphs and as mating graphs) have long been studied in the context of various graph colorings, graph homomorphisms, graph domination, and mating systems since being first considered by Sabidussi in 1961. We also show how to generate graphs that are not pointdetermining but satisfy this property.

Papers on Graph Packing:
 Extremal Graphs for a Graph Packing Theorem of Sauer and Spencer, (with A. Kostochka), Combinatorics, Probability and Computing, Volume 16, 2007, 409417.
summary:
Let G, H be graphs with maximum degrees D(G), D(H), and orders n(G), n(H) at most n. G and H are said to pack if there exist injective mappings of the vertex sets into [n], such that the images of the edge sets do not intersect. In other words, either G or H is isomorphic to a subgraph of the complement of the other. The concept of graph packing generalizes various extremal graph problems, including problems on existence of fixed subgraphs (such as the Hamiltonian Cycle problem), forbidden subgraphs (Turantype problems), and equitable coloring. One of the classical results in this area was by Sauer and Spencer (1978) : if 2D(G)D(H) < n then G and H pack.
We characterize the graphs that achieve equality in the condition on maximum degrees as given in the SauerSpencer result for packing of graphs. We show that: If 2D(G)D(H) ≤ n, then G and H do not pack if and only if one of G or H is a perfect matching and the other either is a complete bipartite graph of (n/2) vertices in each partite set with (n/2) odd, or contains a complete graph of order (1+ n/2). This gives the SauerSpencer theorem as a corollary. This result can be thought of as small step towards the wellknown BollobasEldridge conjecture (see below).
 On a Graph Packing Conjecture of Bollobas, Eldridge, and Catlin, (with A. Kostochka and G.Yu), Combinatorica, Volume 28, 2008, 469485.
summary:
See the definition of graph packing and related notation in the summary above. One of the earliest results in this area was by Sauer and Spencer (1978) : if 2D(G)D(H) < n then G and H pack. The main conjecture in the area was made by Bollobas and Eldridge in 1978, and independently by Catlin in 1974, as an extension of the SauerSpencer result: if (D(G)+1)(D(H)+1) ≤ n+1 then G and H pack. If true, this conjecture would be sharp, and would be a considerable extension of the HajnalSzemeredi theorem on equitable colorings. The conjecture has only been proved when D(G) ≤ 2, or D(G) = 3 and n is huge, and for some special families of graphs.
This paper focuses on proving a result of the form : for a fixed t in [0,1], (D(G)+1)(D(H) +1) ≤ (n/2)(1+t)+1 implies G and H pack. For t=0, this is essentially the SauerSpencer result, while t=1 gives the BEC conjecture. Thus, for any t>0 this would improve the SauerSpencer result and make progres towards the BEC conjecture. We have proved this result for t=0.2. That is, we have essentially improved the bound on the product of maximum degrees in the SauerSpencer theorem from (0.5)n to (0.6)n. Even in 2020, this remains the best progress towards BollobasEldridgeCatlin conjecture.
 Packing of Graphic ntuples, (with A. Busch, M. Ferrara, S. Hartke, M.S. Jacobson, and D.B. West), Journal of Graph Theory, Vol 70, 2012, 2939.
summary:
Let p=(p_{1},...,p_{n}) and q=(q_{1},...,q_{n}) be graphic ntuples (they need not be monotone). We say that p and q pack if there exist edgedisjoint graphs G and H with vertex set v_{1}, ..., v_{n} such that the degrees of v_{i} in G and H are p_{i} and q_{i}, respectively. When packing graphs, we permit permuting the vertices to make G and H "fit together", but when packing sequences, we do not permit the sequences to be permuted. From an optimization pointofview, this can be thought of as an feasibility problem. This problem is related to certain multicommodity flow problems with applications in supply chain/logistics, and even xray tomography. However, packing even 2 bipartite sequences is NPhard.
We prove that two graphic ntuples pack if D ≤ sqrt(2dn)(d1), where D and d denote the largest and smallest entries in p+q (strict inequality when d=1); furthermore, the bound is sharp. If the two graphic sequences do not share any 0 terms then D < sqrt(2n) implies the two sequences pack. This can be thought of as SauerSpencer type of packing result (see the summary of the first packing paper above).
Kundu's Theorem (1973) characterizes when a graphic ntuple has a realization containing a spanning subgraph that is kregular. We consider extensions of Kundu's Theorem and conjecture the stronger statement that in fact when n is even there is a realization containing k edgedisjoint 1factors (that is, a kedgecolorable kfactor). We prove the conjecture when the largest entry is at most 1+(n/2). We also prove the more difficult result that the conjecture holds when k ≤ 3, by proving the stronger statement that there is a realization containing a kfactor that has two edgedisjoint 1factors.
 A Generalization of the Graph Packing Theorems of SauerSpencer and Brandt, (with B. Reiniger), Combinatorica, 42 (2022), 1347–1356.
summary:
We prove a common generalization of the celebrated SauerSpencer packing theorem and a theorem of Brandt concerning finding a copy of a tree inside a graph: Let G be a graph of maximum degree D, and H a cdegenerate graph, both on n vertices, with degree sequences (g_{1}, ..., g_{n}) and (h_{1}, ..., h_{n}) in nonincreasing order, respectively. If ∑_{i=1 to D}(h_{i}) + ∑_{i=1 to c}(g_{i}) < n then G and H pack.
This proof leads to the characterization of the extremal graphs in the case of Brandt's theorem: If G is a graph of maximum degree D, and F is a forest, both on n vertices, and 3D+l*(F) ≤ n, then G and F pack, unless n is even, G is a perfect matching, and F is a star with (n1) leaves; where l*(F), number of "excess" leaves, is the difference between the number of leaves and twice the number of nontrivial components of F.

Papers on Classical Coloring of Graphs:
 See above for an application of equitable coloring of the dependency graph of random variables as a means to study their order statistics in:
New Global Optima Results for the Kauffman NK Model: Handling Dependency, (with S.H. Jacobson),
Mathematical Programming, Special issue on 'Optimization under Uncertainty', Volume 108, 2006, 475494.
 Distinguishing Chromatic Number of Cartesian Products of Graphs, (with J. Choi^ and S. Hartke), SIAM Journal on Discrete Mathematics, Volume 24, 2010, 82100.
summary:
The distinguishing chromatic number of a graph G, χ_{D}(G), is the least number of colors needed for a proper coloring of G with the property that the only colorpreserving automorphism of G is the identity. That is, we want to give a proper coloring of a graph that breaks all its symmetries, so that the coloring together with the structure of the graph uniquely determines the vertices. This can be thought of as an exact encoding of the vertices using only a proper coloring. It is a common extension of both the chromatic number and the distinguishing number of graphs.
The chromatic number, χ(G), is an immediate lower bound for χ_{D}(G). We show that χ_{D}(G) can be surprisingly at most one worse than χ(G) for G a Cartesian power of any graph. The main theorem is : For every graph G, there exists a constant d(G) (explicitly given) such that for all d ≥ d(G), χ_{D}(G^{d}) ≤ χ(G)+1, where G^{d} denotes the Cartesian product of d copies of G. Using our proof techniques, we also find the distinguishing chromatic number for Hypercubes, Hamming graphs (Cartesian products of complete graphs), and Cartesian products of complete multipartite graphs.
 Guarding Orthogonal Art Galleries with Holes, (with Y. Jo^), technical report.
summary:
The original art gallery problem (V. Klee, 1973) asked for the minimum number of guards sufficient to see every point of the interior of an nvertex simple polygon (Art Gallery). Chvatal (1975) proved that (n/3) guards are always sufficient. If all the edges of the given simple polygon are either horizontal or vertical, then such a polygon is called an orthogonal gallery. Kahn, Klawe and Kleitman (1983) proved that (n/4) guards are sufficient for such a nvertex orthogonal gallery. We study orthogonal gallery with holes, i.e., an orthogonal polygon enclosing some other orthogonal polygons called holes (interior of each hole is empty, so these holes model natural obstructions to visibility in the interior of the polygon). In 1982, Shermer conjectured that any orthogonal polygon with n vertices and h holes can be guarded by (n+h)/4 vertex guards. This conjecture remains open. The best previous result shows that (n+2h)/4 such guards suffice (O'Rourke 1987).
We improve this bound to (n+(5/3)h)/4 using a graph coloring argument over a geometric graph. This is still the best known bound.
 On Graph FallColoring  Existence and Constructions, (with C. Mitillos^), Graphs and Combinatorics, 35 (2019), 16331646.
summary:
Graph FallColoring, also known as Idomatic Partition or Independent Domatic Partition of graphs, was formally introduced by Dunbar, Hedetniemi, Hedetniemi, Jacobs, Knisely, Laskar and Rall in 2000 as an extension of both Graph Coloring and Graph Domination. It asks for a partition of the vertex set of a given graph into independent dominating sets, or equivalently into maximal independent sets. We study two fundamental questions related to this concept: when such a partition of vertices can exist, and how it relates to a proper coloring.
We construct graphs with a large number of possible Fallcolorings, and characterize their independent dominating sets. We use this construction to create graphs with arbitrarily large Fallsets (collection of k such that the graph has a fall coloring with k colors), whose elements have arbitrarily large gaps between them; in fact the Fallsets can be arbitrarily long arithmetic sequences with prescribed common difference. Furthermore, by extending our construction, we answer a question of Dunbar et al. (2000) by constructing a family of graphs with arbitrarily far apart chromatic number and fallchromatic number.
We give a lower bound on the minimum degree which ensures that every kcoloring of a given kcolorable graph is also a kfallcoloring. This can be thought of as an improvement of an old result of Bollobas (1978) on sufficient minimum degree for uniquely colorable graphs. Moreover, this result shows the existence of k disjoint independent dominating sets in a dense graph containing k disjoint independent sets; a result along the lines of a similar one by Erdos et al. (1982) for the existence of two disjoint independent dominating sets. We then prove the sharpness of this bound, by constructing a graph with lower minimum degree and no kfallcoloring. We also construct a family of graphs whose set of kcolorings, for all k, includes both nonfallcolorings and fallcolorings, illustrating the complex relation between fall and nonfall colorings of a graph even when both exist.
 On Graph FallColoring  Operators and Heredity, (with C. Mitillos^), Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 106 (2018), 125151.
summary:
Graph fallcoloring, also known as Idomatic partition or Independent Domatic partition of graphs, was formally introduced by Dunbar, Hedetniemi, Hedetniemi, Jacobs, Knisely, Laskar and Rall in 2000 as an extension of both graph coloring and graph domination. It asks for a partition of the vertex set of a given graph into independent dominating sets, or equivalently into maximal independent sets. Since a fall coloring of a graph need not always exist, the question of its existence is a fundamental problem.
We study the effect that various graph operators have on fallcolorability. We consider binary graph operators such as the Cartesian, categorical, rooted, strong, and lexicographic products of graphs, as well as the graph join operation. We also study unary graph operators such as the power operators and the related middle and total graph operators, and the generalized Mycielski operators. We apply our results to prove a part of the ErdosFaberLovasz conjecture, as well as reformulate the conjecture in terms of fallcoloring and hypergraphs. We define and study the notion of edit distance of graph to a fallcolorable supergraph using the edge insertion operator, and show that this is an NPcomplete problem.
We see the full spectrum of effects that these graph operators have on fallcolorability.
Preservation of the fall colorability of the input graphs: the Cartesian, rooted, and categorical products.
Modification of the fall colorability: the strong and lexicographic products, the join, and some of the generalized Mycielski operators.
Elimination of the fall colorability: the usual Mycielski operator, as well as repeated applications of the Middle graph operator.
Creation of fall colorability when applied to specific nonfallcolorable graphs: certain power operators, Cartesian power, or by edge insertion.
 A Note on the Chromatic Number of the Square of Kneser Graph K(2k+1,k), (with JH. Kang), Discrete Mathematics, 343 (2020), article 111630.
summary:
Kneser graphs have been wellstudied for their rich structural and extremal properties, especially with regard to coloring problems since at least 1955 when M. Kneser formulated the problem of finding the chromatic number of what came to be called the Kneser graph. This problem was famously solved by Lovasz (and independently by Barany) in 1978 using topological methods. The vertices of Kneser graph K(n,k) are the subsets of [n] of cardinality k, two vertices are adjacent if and only if they are disjoint. The square G^{2} of a graph G is defined on the vertex set of G with two vertices adjacent if their distance in G is at most 2.
Zoltan Furedi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first nontrivial problem arises when n=2k+1, that is the Odd graph. This remains an open problem and it is believed that the chromatic number χ(K^{2}(2k+1,k)) = 2k+c where c is a constant. The best known upper bounds are by Kim and Park: (8k/3) + (20/3) for k ≥ 3 (2014) and (32k/15) + 32 for k ≥ 7 (2016). Kim and Park conjecture that χ(K^{2}(2k+1,k)) ≤ 2k + 2 for all k large enough.
We employ graph homomorphisms, Cartesian products of graphs, and linear congruences integrated with combinatorial arguments to prove an upper bound: 2(k+1) + 2log_{2}(k) for k ≥ 3, which matches the conjectured leading term of 2k. This is the best known upper bound till date. We also show that the conjecture is true, with a bound of 2k+2, for all k such that k+1 is a power of 2.

Papers on List Coloring of Graphs:
 On AlonTarsi Number and Chromaticchoosability of Cartesian Products of Graphs, (with J. Mudrock^), The Elect. Journal of Combinatorics, 26 (2019), article P1.3.
summary:
We study the list chromatic number of Cartesian products of graphs through the AlonTarsi number as defined by Jensen and Toft (1995) in their seminal book on graph coloring problems. The AlonTarsi number of G, AT(G), is the smallest k for which there is an orientation, D, of G with max indegree k1 such that the number of even and odd circulations contained in D are different. It is known that χ(G) ≤ χ_{L}(G) ≤ χ_{P}(G) ≤ AT(G), where χ(G) is the chromatic number, χ_{L}(G) is the list chromatic number, and χ_{P}(G) is the paint number of G. In this paper we find families of graphs G and H such that χ(G□H) = AT(G□H), reducing this sequence of inequalities to equality. Here G□H denotes the Cartesian product of the graphs G and H.
We show that the AlonTarsi number of the Cartesian product of an odd cycle and a path is always equal to 3 (this proof is featured in two forthcoming textbooks on Combinatorial Nullstellensatz and on Graph Coloring Methods). This result is then extended to show that if G is an odd cycle or a complete graph and H is a graph on at least two vertices containing the Hamilton path w1, w2, ...., wn such that for each i, wi has a most k neighbors among the vertices preceding it, then AT(G□H) ≤ D(G)+k, where D(G) is the maximum degree of G. We discuss other extensions for G□H, where G is such that V(G) can be partitioned into odd cycles and complete graphs, and H is a graph containing a Hamiltonian path. We apply these bounds to get chromaticchoosable Cartesian products, e.g. when G is the join of a clique and an odd cycle and H is a path, in fact we show that these families of graphs have χ(G) = AT(G), improving previously known bounds.
 Criticality, The List Color Function, and List Coloring the Cartesian Product of Graphs, (with J. Mudrock^), Journal of Combinatorics, Volume 12 (2021), 479514.
summary:
We introduce a notion of colorcriticality in the context of chromaticchoosability, χ_{L}(G)=χ(G), whereχ(G) is the chromatic number and χ_{L}(G) is the list chromatic number of G. We define a graph G to be strong kchromaticchoosable if χ(G)=k and every (k1)listassignment for which G is not listcolorable has the property that the lists are the same for all vertices. That is the usual coloring is, in some sense, the obstacle to better listcoloring. We prove basic properties of strongly chromaticchoosable graphs such as chromaticchoosability and vertexcriticality, and we construct infinite families of strongly chromaticchoosable graphs including cliques, odd cycles, and many more.
Using results on unique list colorability based on Combinatorial Nullstellensatz, we derive a sufficient condition for the existence of at least two list colorings of strongly chromaticchoosable graphs and use it to show that: if M is a strong kchromaticchoosable graph with E(M) at most V(M)(k2) and H is a graph that contains a Hamilton path, w1, w2, ...., wn, such that for each i, wi has a most r neighbors among the vertices preceding it, then χ_{L}(M□H) ≤ k + r  1. This shows chromatic choosability for every M when H is a path (giving sharpness of the bound for r=1). We show that this bound is sharp for all r ≥ 1 by generalizing the theorem to apply to H that are (M,r)Cartesian accommodating. This is a notion we define with the help of the list color function, P_{L}(G,k), the list analogue of the chromatic polynomial, that counts the number of different list colorings guaranteed for G with every klistassignment. The sharpness examples are constructed recursively as: S(M,B',r) that glues together P_{L}(M,k+r2) disjoint copies of S(M,B',r1), starting with S(M,B',1)=B', a subdivision of a star with P_{L}(M,k)1 leaves. This gives us recursive constructions of large chromaticchoosable graphs.
We use the list color function to determine the list chromatic number of certain starlike graphs, here K_{(1,s)} is the star with s leaves: χ_{L}(M□K_{(1,s)}) = k if s < P_{L}(M,k), or k+1 if s ≥ P_{L}(M,k), where M is any strong kchromaticchoosable graph. We use the results that P_{L}(M,k)=P(M,k) when M is an odd cycle (C_{(2l+1)}), complete graph (K_{n}), or the join of an odd cycle with a complete graph to prove:
χ_{L}(C_{(2l+1)}□K_{(1,s)}) transitions from 3 (its chromatic number) to 4 at exactly s= 2^{(2l+1)}2; χ_{L}(K_{n}□K_{(1,s)}) transitions from n (its chromatic number) to n+1 exactly at s= n!; and χ_{L}((K_{n}∨C_{(2l+1)}□K_{(1,s)}) transitions from n+3 (its chromatic number) to n+4 at s=(1/3) (n+3)! (4^{l}1). We can extend this result to get chromatic choosability when the second factor is a subdivision of a star or an appropriately bounded rooted tree.
 List Coloring a Cartesian Product with a Complete Bipartite Factor, (with J. Mudrock), Graphs and Combinatorics, 35 (2019), 15711583.
summary:
This paper is a continuation of the paper above "Criticality, The List Color Function, and List Coloring the Cartesian Product of Graphs".
We study χ_{L}(G□K_{(a,b)}), the list chromatic number of the Cartesian product of any graph G on n vertices, and a complete bipartite graph with partite sets of size a and b. We have two motivations. A classic result on the gap between list chromatic number and the chromatic number tells us χ_{L}(K_{(a,b)}) = 1 + a if and only if b ≥ a^a. Since χ_{L}(K_{(a,b)}) ≤ 1 + a for any b, this result tells us the values of b for which χ_{L}(K_{(a,b)}) is as large as possible and far from its chromatic number χ(K_{(a,b)})=2. In this paper we seek to understand when χ_{L}(G□K_{(a,b)}) is far from χ(G□K_{(a,b)}) = max{χ(G), 2}. It is easy to show χ_{L}(G□K_{(a,b)}) ≤ χ_{L}(G)+a. Borowiecki et al. (2006) showed that this bound is attainable if b is sufficiently large; specifically, χ_{L}(G□K_{(a,b)}) = χ_{L}(G)+a whenever b ≥ (χ_{L}(G)+a1)^{(an)}.
Given any graph G and a, we wish to determine f(G,a), the smallest b such that χ_{L}(G□K_{(a,b)}) = χ_{L}(G)+a. In this paper we show that the list color function, P_{L}(G,k), the list analogue of the chromatic polynomial, that counts the number of different list colorings guaranteed for G with every klistassignment, provides the right concept and tool for making progress on this problem. We prove that for any graph G, χ_{L}(G□K_{(a,b)}) = χ_{L}(G)+a whenever b ≥ (P_{L}(G, χ_{L}(G)+a1))^{a}, a sharp bound that is a vast improvement on the previous results.
The argument can be generalized to give us conditions when χ_{L}(G□H) is guaranteed to be far from χ(G□H) for any bipartite graph H. Let H be a bipartite graph with partite sets A and B where A=a and B=b. Let d = min degree of vertices in B. If b ≥ (P_{L}(G, χ_{L}(G)+d1))^a, then χ_{L}(G□H) ≥ χ_{L}(G)+d.
We show these bounds are sharp: if M is a strong kchromatic choosable graph and k ≥ a+1, then χ_{L}(M□ K_{(a,b)}) = χ_{L}(G)+a if and only if b ≥ (P_{L}(M, χ_{L}(M)+a1))^{a}. This is a generalization of results in the previous paper, see the summary above. This can be applied to get explicit bounds, e.g. f(C_{(2l+1)},2) = (P_{L}(C_{(2l+1)},4))^{2} = 9(9^{l}1)^{2}; and f(K_{n},a)= (P_{L}(K_{n}, n+a1))^{a} = ((n+a1)!/(a1)!)^{a}. We also prove a general lower bound on f(G,a) for strongly chromaticchoosable graphs.
 Proportional Choosability: a new list analogue of equitable coloring, (with J. Mudrock^, M. Pelsmajer, R. Reiniger), Discrete Mathematics, 342 (2019), 23712383.
summary:
In 2003, Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability which prescribes an upper bound on the size of each color class in the list coloring (unlike equitable coloring which prescribes both an upper and lower bound on the sizes of the color classes). In this paper, we motivate and define a new list analogue of equitable coloring called proportional choosability. For each color c in an list assignment L of a graph, let n(c), multiplicity of c, be the number of vertices v whose list L(v) contains c. Given a klistassignment L of a graph G, proportional Lcoloring of G is a proper Lcoloring in which each color c is used either ceiling or floor of n(c)/k times. Note that this gives exactly the definition of equitable coloring when the same list of size k is assigned to all vertices. A graph G is proportionally kchoosable if a proportional Lcoloring of G exists whenever L is a kassignment for G.
We use matching theory to show that proportional choosability is monotonic in k, meaning that if G is proportionally kchoosable, then it must be proportionally (k+1)choosable as well. We also show that proportional kchoosability is monotone, meaning that if H is a subgraph of G and G is proportionally kchoosable, then H is also proportionally kchoosable. These results are surprising, considering that equitable coloring and equitable list coloring do not have these nice properties. We give an algorithmic argument to convert an equitable Lcoloring with some additional restrictions into a proportional Lcoloring for a kassignment L of G with every color having multiplicity less than 2k, which helps us prove that any graph G is proportionally kchoosable whenever k ≥ D(G) + V(G)/2, where D(G) is the max degree of G. We use matching theory to completely characterize the proportional choosability of stars and the disjoint union of cliques. Note that handling disconnected graphs is still a challenge, just like in equitable choosability.
 A Simple Characterization of Proportionally 2Choosable Graphs, (with J. Mudrock^, M. Pelsmajer, R. Reiniger), Graphs and Combinatorics, 36 (2020), 679687.
summary:
We recently introduced proportional choosability, a new list analogue of equitable coloring. Like equitable coloring, and unlike list equitable coloring (a.k.a. equitable choosability), proportional choosability bounds sizes of color classes both from above and from below. See the definitions in the previous paper's summary above. Here we show that a graph is proportionally 2choosable if and only if it is a linear forest such that its largest component has at most five vertices and all of its other components have two or fewer vertices. We also construct counterexamples that show that characterizing equitably 2choosable graphs is still open. Some intriguing questions about proportional choosability of paths are proposed.
 Bounding the List Color Function Threshold from Above, (with A. Kumar^, A. Liu^, J. Mudrock, P. Rewers^, P. Shin^, M.S. Tanahara^, K. To^), Involve: A journal of mathematics, Volume 16, 2023, 849–882.
summary:
In 1912 Birkhoff introduced the notion of the chromatic polynomial P(G,m), which counts the number of proper colorings with m colors in a graph G. The notion of chromatic polynomial was extended to list coloring in the early 1990s by Kostochka and Sidorenko. The list color function, P_{L}(G,m), the list analogue of the chromatic polynomial, that counts the number of different list colorings guaranteed for G with every mlistassignment. It follows that P_{L}(G,m) ≤ P(G,m). In general, the list color function can differ significantly from the chromatic polynomial for small values of m. In 1992, Donner showed that for any graph G there is a k such that P_{L}(G,m) = P(G,m) whenever m ≥ k. The list color function threshold of G, denoted t(G) is the smallest k ≥ χ(G) such that P_{L}(G,m) = P(G,m) whenever m ≥ k.
In 2009, Thomassen showed that for any graph G, t(G) ≤ V(G)^{10} + 1. Then, in 2017, Wang, Qian, and Yan significantly improved it to t(G) ≤ (1.14) E(G).
In an earlier work, it was proved that there is a positive constant c such that for each l ≥ 16, t(K_{2,n}) ≥ c sqrt(n), and it was conjectured that this lower bound captures the behavior of t(K_{2,n}).
In this paper we develop tools for bounding the list color function threshold of complete bipartite graphs from above. We show that for any n, t(K_{2,n}) ≤ (n + 2.05)/1.24. Interestingly, our proof makes use of classical results from Analysis such as Rolle’s Theorem and Descartes’ Rule of Signs. We also ask questions and prove some results regarding enumerativechromatic choosability of K_{2,n}.
 On the List Color Function Threshold, (with A. Kumar^, J. Mudrock, P. Rewers^, P. Shin^, K. To^), Journal of Graph Theory, Vol 105, 2024, 386397.
summary:
In 1912 Birkhoff introduced the notion of the chromatic polynomial P(G,m), which counts the number of proper colorings with m colors in a graph G. The notion of chromatic polynomial was extended to list coloring in the early 1990s by Kostochka and Sidorenko. The list color function, P_{L}(G,m), the list analogue of the chromatic polynomial, that counts the number of different list colorings guaranteed for G with every mlistassignment. It follows that P_{L}(G,m) ≤ P(G,m). In general, the list color function can differ significantly from the chromatic polynomial for small values of m. In 1992, Donner showed that for any graph G there is a k such that P_{L}(G,m) = P(G,m) whenever m ≥ k. The list color function threshold of G, denoted t(G) is the smallest k ≥ χ(G) such that P_{L}(G,m) = P(G,m) whenever m ≥ k.
In 2009, Thomassen showed that for any graph G, t(G) ≤ V(G)^{10} + 1. Then, in 2017, Wang, Qian, and Yan significantly improved it to t(G) ≤ (1.14) E(G).
In 2009, Thomassen asked whether there a universal constant C such that for any graph G, t(G) ≤ χ_{L}(G) + C? We show that the answer to this question is no in a fairly strong sense by proving that there is a constant c such that for each l ≥ 16, t(K_{2,n})  χ_{L}(K_{2,n}) ≥ c sqrt(n). We conjecture that this lower bound captures the behavior of t(K_{2,n}).
In light of the bound of Wang, Qian, and Yan, Thomassen's Question, and our Theorem, it is natural to study the asymptotic behavior of the list color function threshold as the size of the graphs we consider tends toward infinity. We define the extremal functions d_{max}(m) = max {t(G)  χ_{L}(G) : G is a graph with at most m edges} and t_{max}(m) = max {t(G) : G is a graph with at most m edges}. By our Theorem and the bound of Wang, Qian, and Yan, we know that there exist constants such that c_{1} sqrt(m) ≤ d_{max}(m) ≤ c_{2} m for large enough m, and c_{3} sqrt(m) ≤ t_{max}(m) ≤c_{2} m for large enough m. We ask what is the asymptotic behavior of d_{max}(m) and t_{max}(m)? In particular, if t_{max}(m) grows faster than sqrt(m) then d_{max}(m) will be asymptotic to t_{max}(m).
 Flexible list colorings: Maximizing the number of requests satisfied, (with R. Mathew, J. Mudrock, M. Pelsmajer), Journal of Graph Theory, 106 (2024), 887906.
summary:
Details forthcoming.
In the meantime, checkout Section 1 of the paper.
 On strongly and robustly critical graphs, (with A. Bernshteyn, J.Mudrock, G. Sharma^), submitted for publication.
summary:
Details forthcoming.
In the meantime, checkout Sections 1 of the paper for a detailed overview.
 Counting packings of listcolorings of graphs, (with J. Mudrock), Submitted for publication.
summary:
Given a list assignment for a graph, list packing asks for the existence of multiple pairwise disjoint list colorings of the graph. Several papers have recently appeared that study the existence of such a packing of list colorings. Formally, a proper Lpacking of a graph G of size k is a set of k pairwise disjoint proper Lcolorings of G where L is a list assignment of colors to the vertices of G. In this paper, we initiate the study of counting such packings of list colorings of a graph.
We define P_{l}^{*}(G,q,k) as the guaranteed number of proper Lpackings of G of size k over all list assignments L that assign q colors to each vertex of G, and we let P^{*}(G,q,k) be its classical coloring counterpart. We let P_{l}^{*}(G,q)= P_{l}^{*}(G,q,q) so that P_{l}^{*}(G,q) is the enumerative function for the previously studied list packing number. Note that the chromatic polynomial of G, P(G,q), is P^{*}(G,q,1), and the list color function of G, P_{l}(G,q), is P_{l}^{*}(G,q,1).
Inspired by the wellknown behavior of the list color function and the chromatic polynomial, we make progress towards the question of whether P_{l}^{*}(G,q,k) = P^{*}(G,q,k) when q is large enough. Our result generalizes the recent theorem of Dong and Zhang (2023), that improved results going back to Donner (1992) that answered a question of Kostochka and Sidorenko, about when the list color function equals the chromatic polynomial. Further, we use a polynomial method to generalize recently obtained bounds on the list packing number of sparse graphs like planar graphs and its subfamilies, to exponential lower bounds on the corresponding list packing functions.
 Counting listcolorings of unlabeled graphs, (with J. Mudrock), Submitted for publication.
summary:
The classic enumerative functions for counting colorings of a graph G, such as the chromatic polynomial P(G,k), do so under the assumption that the given graph is labeled. In 1985, Hanlon defined and studied the chromatic polynomial for an unlabeled graph G, P(G, k). Determining P(G, k) amounts to counting colorings under the action of automorphisms of G.
In this paper, we consider the problem of counting list colorings of unlabeled graphs. Unlike previous works, the challenge here is that Burnside's Lemma/ Orbit Counting Lemma is of limited utility in this context. List coloring of graphs is a widely studied generalization of classic coloring that was introduced by Vizing and by Erdos, Rubin, and Taylor in the 1970s. In 1990, Kostochka and Sidorenko introduced the list color function P_{l}(G, k) which is the guaranteed number of list colorings of a labeled graph G over all klist assignments of G. In this paper, we extend Hanlon's definition to the list context and define the unlabeled list color function P_{l}(G, k), of an unlabeled graph G.
In this context, we pursue a fundamental question whose analogues have driven much of the research on counting list colorings and its generalizations: For a given unlabeled graph G, does P_{l}(G, k) = P(G, k) when k is large enough? We show the answer to this question is yes for a large class of unlabeled graphs that include pointdetermining graphs (also known as irreducible graphs and as mating graphs). Pointdetermining graphs (also referred in literature as irreducible graphs and as mating graphs) have long been studied in the context of various graph colorings, graph homomorphisms, graph domination, and mating systems since being first considered by Sabidussi in 1961. We also show how to generate graphs that are not pointdetermining but satisfy this property.

Papers on DPColoring of Graphs:
 Combinatorial Nullstellensatz and DPColoring of Graphs, (with J. Mudrock), Discrete Mathematics, Volume 343 (2020), article 112115.
summary:
We initiate the study of applying the Combinatorial Nullstellensatz to the DPcoloring of graphs even though, as is wellknown, the AlonTarsi theorem does not apply to DPcoloring. The key obstacle to overcome in applying the Combinatorial Nullstellensatz to DPcoloring is: the graph polynomial is typically viewed as a polynomial over the reals which allows us only to prove results in the DPcoloring context on covers that correspond to list assignments. Here we view graph polynomials as polynomials over some appropriate finite field which allows us to apply the Combinatorial Nullstellensatz to certain covers with list sizes bounded by a power of a prime. This flexibility allows us to apply the Combinatorial Nullstellensatz, and the tools derived from it, to many covers that do not correspond to any list assignment and to coloring problems of Slabelings (a farreaching generalization of many coloring problems such as signed colorings, DPcoloring, group coloring, and coloring of gained graphs).
We define the notion of good covers of prime order which allows us to apply the Combinatorial Nullstellensatz to DPcoloring.
We apply these new tools along with the Quantitative Combinatorial Nullstellensatz to DPcoloring of the cones of certain bipartite graphs and uniquely 3colorable graphs. We also extend a result of Akbari, Mirrokni, and Sadjad (2006) on unique list colorability to the context of DPcoloring. We establish a sufficient algebraic condition for a graph G to be 3DPcolorable, and for a connected graph G with cycles, we reduce the number of polynomials to be tested to at most 2^(E(G)V(G)+1). Finally, we completely determine the DPchromatic number of the squares of all cycles.
 On the Chromatic Polynomial and Counting DPColorings of Graphs, (with J. Mudrock), Advances in Applied Mathematics, Volume 123 (2021), article 102131.
summary:
The chromatic polynomial of a graph G, P(G,m), counts the number of proper mcolorings of G. It was introduced by Birkhoff in 1912 to study the fourcolor problem, and is one the central objects in algebraic graph theory. The list color function of graph G, P_{L}(G,m), is a list coloring analogue of the chromatic polynomial that has been studied since before 1992, primarily through comparisons with the corresponding chromatic polynomial. DPcoloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvorak and Postle in 2015, that has been studied extensively since then. Intuitively, DPcoloring considers the worstcase scenario of how many colors we have to use in a list coloring if we no longer can identify the names of the colors.
In this paper, we introduce a DPcoloring analogue of the chromatic polynomial called the DP color function, denoted P_{DP}(G,m), and ask several fundamental open questions about it, making progress on some of them. Motivated by known results related to the list color function, we show that while the DP color function behaves similar to the list color function for some graphs, there are also some surprising differences.
A central result on the list color function states that P_{L}(G,m)=P(G,m) whenever m is large enough, but we will show that for any g ≥ 3 there exists a graph, G, with girth g such that P_{DP}(G,m) < P(G,m) when m is sufficiently large. We also study the asymptotics of P(G,m)  P_{DP}(G,m) for a fixed graph G.
We use probabilistic arguments to prove a sharp lower bound on P_{DP}(G,m) which is the same as the lower bound on P(G,m) when G is bipartite, as claimed by the famous Sidorenko's conjecture on counting homomorphisms from a bipartite graph. This bound along with our other results allow us to show that a natural analogue of Sidorenko's conjecture for the DP color function holds only for trees.
We develop techniques to compute P_{DP}(G,m) exactly and apply them to certain classes of graphs such as chordal graphs (where P_{DP}(G,m)=P(G,m)), unicyclic graphs (where the answer depends on the parity of its girth), and cycles with a chord (where the answer depends on the parities of the lengths of the two maximal cycles properly contained in such a graph). Finally, we make progress towards showing that for any graph G, there is a p such that P_{DP}(G∨K_{p}, m) = P(G∨K_{p}, m) for large enough m.
 Partial DPColoring of Graphs, (with J. Mudrock, M. Pelsmajer), Discrete Mathematics, 344 (2021), article 112306.
summary:
In 1980 Albertson and Berman introduced partial coloring, and then in 2000, Albertson, Grossman, and Haas introduced partial list coloring. Here we initiate the study of partial coloring for DPcoloring (aka, correspondence coloring), a generalization of list coloring introduced by Dvorak and Postle in 2015, that has been studied extensively since then. Intuitively, DPcoloring considers the worstcase scenario of how many colors we have to use in a list coloring if we no longer can identify the names of the colors. The partial tchromatic number of a graph G, denoted A(G,t), is the maximum number of vertices in G that can be colored with t colors. Clearly, A(G,t) ≥ tn/χ(G) for each t in {1, ...., χ(G)}, where χ(G) is the chromatic number of the n vertex graph G. The list coloring version of this concept is the partial tchoice number of a graph G, denoted A_{L}(G,t), the maximum number of vertices that can be properly colored for each tlistassignment. The Partial List Coloring Conjecture, that is still open, states that for any graph G, A_{L}(G,t) ≥ tn/χ_{L}(G) for each t in {1, ...., χ_{L}(G)}, where χ_{L}(G) is the list chromatic number of G. It is now natural to define the partial DP tchromatic number, A_{DP}(G,t), and extend this conjecture to DPcoloring.
We show that while the DPcoloring analogue of the Partial List Coloring Conjecture does not hold, several results on partial list coloring can be extended to the DPcoloring context. We call a graph partially DPnice if it satisfies A_{DP}(G,t) ≥ tn/χ_{DP}(G) for each t in {1, ...., χ_{DP}(G)}, where χ_{DP}(G) is the DPchromatic number of G. We develop a new characterization of 2fold covers and use it to construct several examples of graphs G with χ_{DP}(G)=3 and A_{DP}(G,2) less than 2n/3, including an infinite family of graphs on 5k vertices, and the cube graph Q_{3}. We show that the Wagner graph V_{8} is partially DPnice, A_{DP}(V_{8},2)=6, and that V_{8} has no induced subgraph with DPchromatic number 2 and order at least (2/3)V(V_{8}) which answers a natural open question about partial DP tchromatic number of induced subgraphs.
We can conclude that every connected, subcubic, trianglefree graph, with the unique exception of Q_{3}, is partially DPnice. We use feedback vertex covers to observe that any nontrivial planar graph of girth at least 5 is partially DPnice. We prove several more classes of graphs are partially DPnice, including chordal graphs and seriesparallel graphs. We also consider the join of a graph with a complete graph and prove that: for any graph G, there exists a p such that G∨K_{p} is partially DPnice.
We prove that A_{DP}(G,t) ≥ n/ceiling[χ_{DP}(G)/t] for each t in {1, ...., χ_{DP}(G)}. It follows that for any graph G, the inequality A_{DP}(G,t) ≥ tn/χ_{DP}(G) holds true for at least half of the values of t. The main tool here is a subadditivity lemma: for any graph G and t1, ...., tk, A_{DP}(G,t)) ≤ ∑_{i=1 to k}(A_{DP}(G,ti)) where t = ∑_{i=1 to k}(ti).
 The DP Color Function of Joins and VertexGluings of Graphs, (with J. Becker^, J. Hewitt^, M. Maxfield^, J. Mudrock, D. Spivey^, S. Thomason^, T. Wagstrom^), Discrete Mathematics, 345 (2022), article 113093.
summary:
DPcoloring (also called correspondence coloring) is a generalization of list coloring that has been widely studied in recent years after its introduction by Dvorak and Postle in 2015. As the analogue of the chromatic polynomial P(G,m), the DP color function of a graph G, denoted P_{DP}(G,m), counts the minimum number of DPcolorings over all possible mfold covers. Chromatic polynomials for joins and vertexgluings of graphs are well understood and widely used to build the chromatic polynomials of graphs built through a sequence of such operations, but the effect of these graph operations on the DP color function is not known.
In this paper we make progress on understanding the DP color function of the join of a graph with a complete graph and vertexgluings of certain graphs. We also develop tools to study the DP color function under these graph operations, such as: given vertex disjoint graphs G_{1}, .... G_{n}, we define amalgamated cover, a natural analogue of "gluing" mfold covers of each G_{i} together so that we get an mfold cover for any G formed by vertex gluing the graphs G_{1}, .... G_{n}; and we define separated covers, a natural analogue of "splitting" an mfold cover of any G formed by cliquegluing the graphs G_{1}, .... G_{n} into separate mfold covers for each G_i. And we study the threshold (smallest m) beyond which the DP color function of a graph constructed with these operations equals its chromatic polynomial.
 Nonchromaticadherence of the DP Color Function via Generalized Theta Graphs, (with Manh Vu Bui^, M. Maxfield^, J. Mudrock, Paul Shin^, S. Thomason^), Graphs and Combinatorics Volume 39, 2023, article number 42.
summary:
DPcoloring (also called correspondence coloring) is a generalization of list coloring that has been widely studied in recent years after its introduction by Dvorak and Postle in 2015. The chromatic polynomial of a graph is an extensively studied notion in combinatorics since its introduction by Birkhoff in 1912; denoted P(G,m), it equals the number of proper mcolorings of graph G. Counting function analogues of the chromatic polynomial have been introduced and studied for list colorings: P_{L}, the list color function (1990); DP colorings: P_{DP}, the DP color function (2019), and P_{DP}^{*}, the dual DP color function (2021). For any graph G and m, P_{DP}(G, m) ≤ P_{L}(G,m) ≤ P(G,m) ≤ P_{DP}^{*}(G,m).
A fundamental open question on the list color function asks whether the list color function of a graph and the corresponding chromatic polynomial stay the same after the first point at which they are both nonzero and equal. A function f is chromaticadherent if for every graph G, f(G,a) = P(G,a) for some a ≥ χ(G) implies that f(G,m) = P(G,m) for all m ≥ a. It is not known if the list color function and the DP color function are chromaticadherent. We show that the DP color function is not chromaticadherent by studying the DP color function of Generalized Theta graphs. The tools we develop along with the Rearrangement Inequality give a new method for determining the DP color function of all Theta graphs and the dual DP color function of all Generalized Theta graphs.
 On Polynomial Representations of the DP Color Function: Theta Graphs and Their Generalizations, (with C. Halberg^, A. Liu^, J. Mudrock, P. Shin^, S. Thomason^), Journal of Combinatorics, 15 (2024), 451478.
summary:
The chromatic polynomial of a graph G, P(G,m), counts the number of proper mcolorings of G. It was introduced by Birkhoff in 1912 to study the fourcolor problem, and is one the central objects in algebraic graph theory. The list color function of graph G, P_{L}(G,m), is a list coloring analogue of the chromatic polynomial that has been studied since before 1992, primarily through comparisons with the corresponding chromatic polynomial. DPcoloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvorak and Postle in 2015, that has been studied extensively since then. Intuitively, DPcoloring considers the worstcase scenario of how many colors we have to use in a list coloring if we no longer can identify the names of the colors.
As the analogue of the chromatic polynomial P(G,m), the DP color function of a graph G, denoted P_{DP}(G,m), counts the minimum number of DPcolorings over all possible mfold covers. It is known that from our previous work, unlike the list color function P_{L}(G,m), for any g ≥ 3 there exists a graph, G, with girth g such that P_{DP}(G,m) < P(G,m) when m is sufficiently large. Thus, two fundamental open questions regarding the DP color function are: (i) for which G does there exist an N such that P_{DP}(G,m) = P(G,m) whenever m > N, (ii) given a graph G does there always exist an N and a polynomial p(m) such that P_{DP}(G,m) = p(m) whenever m > N?
Generalized Theta graphs, which have been widely studied for many graph theoretic problems, are the main subject of two classical papers on the chromatic polynomial which include the celebrated result that the zeros of the chromatic polynomials of the Generalized Theta graphs are dense in the whole complex plane with the possible exception of the unit disc around the origin (by including the join of Generalized Theta graphs with an edge this extends to all of the complex plane). It is natural to study the DP color function of these graphs, independent of our motivating questions.
In this paper we give exact formulas for the DP color function of a Theta graph based on the parity of its path lengths. This gives an explicit answer, including the formulas for the polynomials that are not the chromatic polynomial, to both the questions above for Theta graphs. This result illustrates the complex relationship that the DP color function has with the structure of odd and even cycles in a graph. From previous work, we know that girth being even forces P_{DP}(G,m) < P(G,m) when m is sufficiently large, but this result shows girth being odd can lead to complicated behavior. Despite this, in each of the four parity based cases we see that P_{DP}(G,m) equals a polynomial.
We extend this result to Generalized Theta graphs by characterizing the exact parity condition that ensures the DP color function eventually equals the chromatic polynomial. To answer the second question for Generalized Theta graphs, we confirm it for the larger class of graphs with a feedback vertex set of size one. Even though we do not have an explicit formula for the polynomial p(m) we know its three highest degree terms are the same as those of the corresponding chromatic polynomial. Our proof considers a decomposition of the graph G into a star G_{1} and a spanning forest G_{0}. The problem then reduces to carefully counting the number H_{0}colorings of G_{0} that are not Hcolorings of G, where H_{0} is the mfold cover of G_{0} induced by a given mfold H of G.
 A Note on Fractional DPColoring of Graphs, (with D. Dominik^, J.Mudrock), Discrete Mathematics 347 (2024), article 114123.
summary:
Details forthcoming.
In the meantime, checkout Section 1.3 of the paper.
 DPColoring of Cartesian Product of Graphs, (with J. Mudrock, G. Sharma^, Q. Stratton^), Journal of Graph Theory, Volume 103, 2023, 285306.
summary:
DPcoloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvorak and Postle in 2015, that has been studied extensively since then. Intuitively, DPcoloring considers the worstcase scenario of how many colors we have to use in a list coloring if we no longer can identify the names of the colors. Motivated by known results related to list coloring Cartesian products of graphs, we initiate the study of the DPchromatic number of the Cartesian product of any two graphs G and H, denoted by χ_{DP}(G□H). With a simple generalization of list coloring arguments we show that χ_{DP}(G□H) = min{χ_{DP}(G) + col(H), χ_{DP}(H) + col(G)}  1 where col(H) is the coloring number of the graph H.
Most of the paper is focussed on studying the problems arising out of showing the sharpness for this bound, and building tools for lower bounds on the DPchromatic number for this. First, we define the notion of volatile coloring which gives a characterization of the bad covers of the Cartesian product of two graphs with a complete bipartite factor. This is applied to show a large class of sharpness for the basic upper bound above: for any graph G, χ_{DP}(G□K_{(a,b)}) = χ_{DP}(G)+a whenever b ≥ (P_{DP}(G, χ_{DP}(G)+a1))^{a}. Recall that P_{DP}(G,m) is the DP color function of a graph G, DP coloring analogue of the chromatic polynomial, which counts the minimum number of DPcolorings over all possible mfold covers. See our other papers for results on the DP color function.
Building upon this result, in the rest of the paper, we will show evidence that the DP color function is a useful tool in the study of the DPchromatic number of the Cartesian product of graphs. Considering the sharpness of Theorem 4, also inspires us to consider a more general question: given a graph G and a, we wish to determine f(G,a), the smallest b such that χ_{DP}(G□K_{(a,b)}) = χ_{L}(G)+a.
Next, we define canonical labeling and twistedcanonical labeling of covers which give a characterization of the bad covers of odd and even cycles respectively. Using these tools along with volatile coloring, we showing that sharpness Theorem itself is also sharp when G is an even cycle and k = 1; that is, for any m, f(C_{2m+2}, 1) = P_{DP}(C_{2m+2}, 3) = 2^{2m+2}  1.
Finally, we improve the sharpness Theorem when G is a cycle. Using the tools we have described so far, we construct random covers using a combination of random matchings defined using an equivalence relation on an appropriate set of colorings, and matchings defined using canonical and twistedcanonical labelings. We show that there exists an appropriate bad cover by counting the expected number of volatile colorings and applying the bound on volatile colorings for good covers. This improved theorem gives better bounds on f(C_{m}, k) of the form
c_{k} (P_{DP}(C_{m}, k+2) / (k+2))^{k} where the form of c_{k} depends on the parity of the cycle. In particular we get that for any m, f(C_{2m+1}, 1) = P_{DP}(C_{2m+1}, 3)/3 = (2^{2m+1}  2)/3.
 The DP Color Function of CliqueGluings of Graphs, (with M. Maxfield^, J. Mudrock, S. Thomason^), Enumerative Combinatorics and Applications, Volume 4, 2024, article S2R11.
summary:
DPcoloring (also called correspondence coloring) is a generalization of list coloring that has been widely studied in recent years after its introduction by Dvorak and Postle in 2015. As the analogue of the chromatic polynomial P(G,m), the DP color function of a graph G, denoted P_{DP}(G,m), counts the minimum number of DPcolorings over all possible mfold covers. Chromatic polynomials for cliquegluings of graphs, a fundamental graph operation used for characterizing many graph classes, are well understood and widely used to build the chromatic polynomials of graphs constructed through a sequence of such operations, but the effect of these graph operations on the DP color function is not known.
In this paper we study the DP color function of K_{p}gluings of graphs. Recently, Becker et. al. asked whether P_{DP}(G,m) ≤ (Π_{i=1 to n} P_{DP}(G_{i},m))( Π_{i=0 to p1} (mi) )^{n1} whenever m ≥ p, where the expression on the right is the DPcoloring analogue of the corresponding chromatic polynomial formula for a K_{p}gluing of G_{1}, ...., G_{n}. Don and Yang (2021) asked a simpler version of the same question as well. In a recent paper, we showed this inequality holds when p=1 (vertexgluings). In this paper we show this inequality holds for edgegluings (p=2). On the other hand, we show it does not hold for trianglegluings (p=3). These results also resolve the corresponding questions of Dong and Yang (2021). Finally, we show a relaxed version, based on a class of mfold covers that we conjecture would yield the fewest DPcolorings for a given graph, of the inequality holds when p ≥ 3.
 An Algebraic Approach for Counting DP3colorings of Sparse Graphs, (with S. Dahlberg and J. Mudrock), European Journal of Combinatorics, Volume 118, May 2024, 103890.
summary:
DPcoloring (or correspondence coloring) is a generalization of list coloring that has been widely studied since its introduction by Dvorák and Postle in 2015. As the analogue of the chromatic polynomial of a graph P(G,m), the DP color function of a graph G, denoted P_{DP}(G,m), counts the minimum number of DPcolorings over all possible mfold covers. A function f is chromaticadherent if for every graph G, f(G,a) = P(G,a) for some a ≥ χ(G) implies that f(G,m) = P(G,m) for all m ≥ a. It is known that the DP color function is not chromaticadherent, but there are only two known graphs that demonstrate this.
Suppose G is an nvertex multigraph and H is a 3fold cover of G, in this paper we associate with H a polynomial in n variables over the finite field of order 3, so that the number of nonzeros of this polynomial equals the number of Hcolorings of G. We then use a wellknown result of Alon and Furedi on the number of nonzeros of a polynomial to establish a nontrivial and sharp lower bound 3^{n  l/2} on P_{DP}(G,3) when 2n > l =E(G). As an immediate application, consider a nvertex planar graph G of girth at least 5. It is known that χ_{DP}(G) ≤ 3. Since number of edges in G is at most 5n/3, our bound implies P_{DP}(G,3) ≥ 3^{n/6}. This bound gives a major improvement on the previously known bounds of Thomassen (2007) and Postle and SmithRoberge (2022+) on both DPcolor function and the listcolor function of these graphs.
Finally, we use this bound to show that there are infinitely many graphs that demonstrate the nonchromaticadherence of the DP color function.
 A polynomial method for counting colorings of sparse graphs, (with S. Dahlberg and J. Mudrock), submitted for publication.
summary:
The coloring of planar graphs and its subfamilies has a long history starting with the four color problem in the nineteenth century. This history is intertwined with the related conjectures on existence of exponentially many such colorings (as a function of the number of vertices), going back at the least to Birkhoff’s work in 1930, and Birkhoff and Lewis’ enumerative extension of the four color conjecture in 1946 that for any nvertex planar graph G, the chromatic polynomial satisfies P(G, k) ≥ k(k1)(k2)(k3)^{(n3)} for all real numbers k ≥ 4. They proved this is true for k = 5, thus giving exponentially many 5colorings of planar graphs. After Thomassen in 1994 proved all planar graphs are 5choosable, there has been much work done on showing that planar graphs and their subfamilies have exponentially many list kcolorings for appropriate k in {3, 4, 5}. These proofs are typically intricate topological arguments specialized to the family of planar graphs under consideration.
In this paper, we give a unified and simple polynomial method for proving many such exponential lower bounds on the number of colorings
of sparse graphs without requiring any topological assumptions. Our results are set in the general framework of coloring Slabeled graphs, where S is a subset of a symmetric group, which includes classical and many other types of graph coloring as special cases. In fact, for each such choice of S there is a corresponding notion of coloring of a graph. The subset relation on the set of nonempty subsets of the symmetric group, induces a partial order on all these notions of coloring with the socalled DP coloring as the unique maximal element and the classical coloring as a minimal element. Our most general results will give exponential lower bounds on the enumerative functions of all these notions of coloring, as well as list coloring, for any appropriate sparse graph. Application of our lower bounds to families of planar graphs either improve previously known results or are the first such known results. For example, Signed graphs and their colorings have been widely studied since the 1980s but we do not know of any previous results on bounding the number of such colorings.
 DPcoloring of graphs from random covers, (with A. Bernshteyn, D. Dominik^, J.Mudrock), Random Structures & Algorithms, under revision.
summary:
Details forthcoming.
In the meantime, checkout Sections 1.3 and 1.4 of the paper.
 On strongly and robustly critical graphs, (with A. Bernshteyn, J.Mudrock, G. Sharma^), submitted for publication.
summary:
Details forthcoming.
In the meantime, checkout Sections 1 of the paper for a detailed overview.

Papers on Equitable Coloring of Graphs:
 Total Equitable Choosability of Graphs, (with J. Mudrock^, M. Pelsmajer), Graphs and Combinatorics, 34 (2019), 16371649.
summary:
An equitable coloring is a proper coloring of a graph such that the sizes of the color classes differ by at most one. In 1994, Fu conjectured that for any simple graph G, the total graph of G, T(G), is equitably kcolorable whenever k ≥ max{χ(T(G)), D+2}, where χ(T(G)) is the chromatic number of the total graph of G and D is the maximum degree of G. Recall that vertex coloring of T(G) is the simultaneous proper coloring of vertices and edges of G.
We investigate the list coloring analogue, as introduced by Kostochka, Pelsmajer, and West (2003), which prescribes an upper bound on the size of each color class in the list coloring. A graph is equitably kchoosable if it has a proper list coloring whenever vertices have lists of size k, where each color is used on at most V(G)/k vertices. In the spirit of Fu's conjecture, we conjecture that for any simple graph G, T(G) is equitably kchoosable whenever k ≥ max{χ_{L}(T(G)), D+2} where χ_{L}(T(G)) is the list chromatic number of T(G).
We first prove sharp results on equitable choosability of all powers of paths and cycles, verifying the conjecture and more for these graphs. Our main result is the proof of this conjecture for all graphs satisfying D ≤ 2. Note that, it isn't enough to prove equitable kchoosability for every component of a graph. The disconnected case of the proof of our theorem requires development of new a list decomposition tool that should prove useful for other problems in equitable kchoosability of graphs. In fact, we prove equitable 4choosability for graphs where components may be square of any path, square of any cycle on at least 6 vertices, or a copy of K_{4}, and we also prove equitable 3choosability for graphs where each component is a square of a cycle of length divisible by 3 or a square of a path. So we find exactly which total graphs T(G) with D=2 are equitably 3choosable.
 Proportional Choosability: a new list analogue of equitable coloring, (with J. Mudrock^, M. Pelsmajer, R. Reiniger), Discrete Mathematics, 342 (2019), 23712383.
summary:
In 2003, Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability which prescribes an upper bound on the size of each color class in the list coloring (unlike equitable coloring which prescribes both an upper and lower bound on the sizes of the color classes). In this paper, we motivate and define a new list analogue of equitable coloring called proportional choosability. For each color c in an list assignment L of a graph, let n(c), multiplicity of c, be the number of vertices v whose list L(v) contains c. Given a klistassignment L of a graph G, proportional Lcoloring of G is a proper Lcoloring in which each color c is used either ceiling or floor of n(c)/k times. Note that this gives exactly the definition of equitable coloring when the same list of size k is assigned to all vertices. A graph G is proportionally kchoosable if a proportional Lcoloring of G exists whenever L is a kassignment for G.
We use matching theory to show that proportional choosability is monotonic in k, meaning that if G is proportionally kchoosable, then it must be proportionally (k+1)choosable as well. We also show that proportional kchoosability is monotone, meaning that if H is a subgraph of G and G is proportionally kchoosable, then H is also proportionally kchoosable. These results are surprising, considering that equitable coloring and equitable list coloring do not have these nice properties. We give an algorithmic argument to convert an equitable Lcoloring with some additional restrictions into a proportional Lcoloring for a kassignment L of G with every color having multiplicity less than 2k, which helps us prove that any graph G is proportionally kchoosable whenever k ≥ D(G) + V(G)/2, where D(G) is the max degree of G. We use matching theory to completely characterize the proportional choosability of stars and the disjoint union of cliques. Note that handling disconnected graphs is still a challenge, just like in equitable choosability.
 A Simple Characterization of Proportionally 2Choosable Graphs, (with J. Mudrock^, M. Pelsmajer, R. Reiniger), Graphs and Combinatorics, 36 (2020), 679687.
summary:
We recently introduced proportional choosability, a new list analogue of equitable coloring. Like equitable coloring, and unlike list equitable coloring (a.k.a. equitable choosability), proportional choosability bounds sizes of color classes both from above and from below. See the definitions in the previous paper's summary above. Here we show that a graph is proportionally 2choosable if and only if it is a linear forest such that its largest component has at most five vertices and all of its other components have two or fewer vertices. We also construct counterexamples that show that characterizing equitably 2choosable graphs is still open. Some intriguing questions about proportional choosability of paths are proposed.
 On Equitable List Arboricity of Graphs, (with J. Mudrock, M. Pelsmajer), The Australasian Journal of Combinatorics, 80 (2021), 419441.
summary:
Equitable list arboricity, introduced by Zhang in 2016, generalizes the notion of equitable list coloring by requiring each color class to be acyclic (instead of an independent set), in addition to the usual upper bound on the size of each color class. G is equitably klist arborable if an equitable, arborable list coloring of G exists for every list assignment for G that associates with each vertex in G a list of k available colors.
Zhang conjectured that any graph G is equitably klist arborable for each k satisfying k ≥ ceiling[(1+D(G))/2], where D(G) is the maximum degree of G. We verify this conjecture for powers of cycles by applying a new lemma, a general tool for recognizing a set S of vertices in a graph G and its list coloring that would allow an extension of an equitable, arborable list coloring of GS to an equitable, arborable list coloring of G. This tool is also applied to give improved colorings for powers of a path.
We also propose a stronger version of Zhang's Conjecture for certain connected graphs: any connected graph G is equitably klist arborable for each k satisfying k ≥ ceiling[D(G)/2] provided G is neither a cycle nor a complete graph of odd order. We verify this stronger version of Zhang's Conjecture for powers of paths, 2degenerate graphs, and certain other graphs.
We use probabilistic and algorithmic arguments to show that if G is equitably klist arborable it does not necessarily follow that G is equitably (k+1)list arborable which addresses a question of DrgasBurchardt et al. (2018). We also show that it is not necessary that if a graph G is equitably klist arborable then G is also equitably vertex karborable.
 Equitable Choosability of Disjoint Unions of Stars, (with J. Mudrock, T. Wagstrom^), Graphs and Combinatorics, 38 (2022), article 163.
summary:
Equitable kchoosability is a list analogue of equitable kcoloring introduced by Kostochka, Pelsmajer, and West in 2003, which prescribes an appropriate upper bound on the size of each color class in the list coloring. See the definitions in the paper summaries above. It is known that if vertex disjoint graphs G and H are equitably kchoosable, the disjoint union of G and H may not be equitably kchoosable. Also, unlike many other variants of list coloring problems, a complete characterization of equitably 2choosable graphs is not known, and in general not much is known about equitable kchoosability for small k. Here, we study these problems under the equitable choosability of the disjoint union of stars.
Perhaps surprisingly, since most coloring problems with 2 colors or on stars tend to be easy, we show that determining whether the disjoint union of n stars is equitably choosable is NPcomplete when the same list of two colors is assigned to every vertex. We completely determine when the disjoint union of 2 arbitrary stars is equitably 2choosable. This makes progress on the task of identifying which graphs are equitably 2choosable, and also shows that there are only 14 equitably 2choosable graphs (up to isomorphism) that are the disjoint union of two stars, unlike the infinitely many equitably 2colorable graphs that are the disjoint union of two stars. We completely determine when the disjoint union of n identical stars is equitably 2choosable, with the answer surprisingly depending on the parity of n. We use an extremal choice of a partial list coloring that minimizes the difference of the cardinalities of the sets of uncolored vertices in the two stars, along with a greedy partial list coloring process, to prove a sharp sufficient condition for the equitable kchoosability of two stars for arbitrary k.
Select Presentations
Note that the talks below might contain errors and may not match with the final version of the corresponding papers.