I am a member of the Discrete Applied Math group at IIT. My research interests lie, broadly speaking, in Discrete Mathematics and Operations Research, especially Graph Theory, Discrete/ Network Optimization, and related mathematical/ statistical models and algorithms, and interdisciplinary applications in Transportation Networks, Computer Science, and ECE (Power Networks and Optimization). I am also interested in the ethical aspects of mathematical and optimization models, and particularly in equitable allocation of resources.
Discrete optimization models arise naturally in all branches of discrete mathematics and their applications. My motivation is to develop the understanding of hard optimization problems through a variety of approaches - using probabilistic and combinatorial tools to tackle problems, developing and analyzing the complexity of exact and approximation algorithms, developing both practical and theoretical aspects of heuristics, and understanding local search algorithms and multi-objective optimization. I work with collaborators in Computer Science, in Design, and in Engineering to apply these methodologies to interdisciplinary applications.
My past research has included topics in Stochastic Combinatorial Optimization, Deterministic Combinatorial Optimization, Network Optimization, Exact Combinatorial Algorithms, Meta-Heuristics, Local Search Landscapes, Multi-objective Discrete Optimization.
In the recent years, I have focussed on algorithms related to Graph Optimization, Interdependent network models, Robust optimization for network models, Design of transportation/ health networks with regard to social equity, accessibility, etc.
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) p-nary 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 NP-hard global optimization problem into a stochastic network model that is closely related to two well-studied 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=N-1 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 N-dimensional 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
This paper generalizes and extends the work from the previous paper that focused on the analysis of the (independent) case K=N-1. It presents new global optima results for the NK model by developing tools for handling the dependency between weight functions of different N-vectors 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 = N-a 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).
We study a well-known local-search 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 best-known lower bound, (1/2)n(3/2), on the maximum number of flips possible in a graph with n vertices to (2/25)n2. Note that (1/4)n2 is a trivial upper bound. We also prove better upper bounds like [|E(G)|-(1/4)d2], 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.
Consider the NP-hard problem of, given a simple graph G, to find a K4-minor-free subgraph (series-parallel 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 (n-1) edges and any series-parallel graph on n vertices has at most (2n-3) 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.
We introduce a new model and algorithms for optimal highway investment decision-making 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 multi-commodity flow problem defined over the highway network under study with different non-linear 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 highway-investment decision-making.
We complete a computational study of the road network in the Chicago downtown loop area using latest real-life traffic data from I-DOT (Illinois Department of Transportation) to analyze the decision-making 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 decision-making.
We consider a linear relaxation of a generalized minimum-cost 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 well-known 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.
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 optimization-based 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.
We offer a general approach to modeling longitudinal network data, including exponential random graph models (ERGMs), that vary according to certain discrete-time Markov chains. We connect conditional and Markovian exponential families, permutation-uniform 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 closed-form expressions for maximum likelihood estimators. We also introduce exponential random t-multigraph models, motivated by our result on replacing t observations of permutation-uniform Markov chains of graphs with single observations of corresponding multigraphs.
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 in-depth 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 NP-hard on arbitrary graphs become polynomial on outerplanar graphs. An in-depth 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 NP-hard. Hence, instead of solving the problem exactly, we develop polynomial-time 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 non-trivial 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 4-cycles 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 4-cycles would not improve the approximation ratio.
My past research has included topics in Graph Packing, Graph Coloring, MAX-CUT or Largest Bipartite Subgraph problem, Maximum Independent (Stable) Set problem, Maximum Planar subgraph problem, Graph Layout problems.
In the recent years, I have focussed on various graph coloring problems, list coloring problems and its variants, its far reaching generalization called DP-coloring (aka Correspondence coloring), their enumerative counterparts of the chromatic polynomial, namely, the list color function and the DP color function, notions of graph criticality, and building polynomial methods and applying such algebraic techniques including Combinatorial Nullstellensatz and its generalizations.
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 (Turan-type 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 Sauer-Spencer 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 Sauer-Spencer theorem as a corollary. This result can be thought of as small step towards the well-known Bollobas-Eldridge conjecture (see below).
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 Sauer-Spencer 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 Hajnal-Szemeredi 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 Sauer-Spencer result, while t=1 gives the BEC conjecture. Thus, for any t>0 this would improve the Sauer-Spencer 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 Sauer-Spencer theorem from (0.5)n to (0.6)n. Even in 2020, this remains the best progress towards Bollobas-Eldridge-Catlin conjecture.
Let p=(p1,...,pn) and q=(q1,...,qn) be graphic n-tuples (they need not be monotone). We say that p and q pack if there exist edge-disjoint graphs G and H with vertex set v1, ..., vn such that the degrees of vi in G and H are pi and qi, 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 point-of-view, 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 x-ray tomography. However, packing even 2 bipartite sequences is NP-hard.
We prove that two graphic n-tuples pack if D ≤ sqrt(2dn)-(d-1), 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 Sauer-Spencer type of packing result (see the summary of the first packing paper above).
Kundu's Theorem (1973) characterizes when a graphic n-tuple has a realization containing a spanning subgraph that is k-regular. 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 edge-disjoint 1-factors (that is, a k-edge-colorable k-factor). 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 k-factor that has two edge-disjoint 1-factors.
We prove a common generalization of the celebrated Sauer-Spencer 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 c-degenerate graph, both on n vertices, with degree sequences (g1, ..., gn) and (h1, ..., hn) in non-increasing order, respectively. If ∑i=1 to D(hi) + ∑i=1 to c(gi) < 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 (n-1) 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.
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 color-preserving 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(Gd) ≤ χ(G)+1, where Gd 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.
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 n-vertex 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 n-vertex 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.
Graph Fall-Coloring, 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 Fall-colorings, and characterize their independent dominating sets. We use this construction to create graphs with arbitrarily large Fall-sets (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 Fall-sets 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 fall-chromatic number.
We give a lower bound on the minimum degree which ensures that every k-coloring of a given k-colorable graph is also a k-fall-coloring. 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 k-fall-coloring. We also construct a family of graphs whose set of k-colorings, for all k, includes both non-fall-colorings and fall-colorings, illustrating the complex relation between fall and non-fall colorings of a graph even when both exist.
Kneser graphs have been well-studied 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 G2 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 non-trivial problem arises when n=2k+1, that is the Odd graph. This remains an open problem and it is believed that the chromatic number χ(K2(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 χ(K2(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) + 2log2(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.
We study the list chromatic number of Cartesian products of graphs through the Alon-Tarsi number as defined by Jensen and Toft (1995) in their seminal book on graph coloring problems. The Alon-Tarsi number of G, AT(G), is the smallest k for which there is an orientation, D, of G with max indegree k-1 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 Alon-Tarsi 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 chromatic-choosable 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.
We introduce a notion of color-criticality in the context of chromatic-choosability, χ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 k-chromatic-choosable if χ(G)=k and every (k-1)-list-assignment for which G is not list-colorable 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 list-coloring. We prove basic properties of strongly chromatic-choosable graphs such as chromatic-choosability and vertex-criticality, and we construct infinite families of strongly chromatic-choosable 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 chromatic-choosable graphs and use it to show that: if M is a strong k-chromatic-choosable graph with |E(M)| at most |V(M)|(k-2) 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, PL(G,k), the list analogue of the chromatic polynomial, that counts the number of different list colorings guaranteed for G with every k-list-assignment. The sharpness examples are constructed recursively as: S(M,B',r) that glues together PL(M,k+r-2) disjoint copies of S(M,B',r-1), starting with S(M,B',1)=B', a subdivision of a star with PL(M,k)-1 leaves. This gives us recursive constructions of large chromatic-choosable graphs.
We use the list color function to determine the list chromatic number of certain star-like graphs, here K(1,s) is the star with s leaves: χL(M□K(1,s)) = k if s < PL(M,k), or k+1 if s ≥ PL(M,k), where M is any strong k-chromatic-choosable graph. We use the results that PL(M,k)=P(M,k) when M is an odd cycle (C(2l+1)), complete graph (Kn), 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(Kn□K(1,s)) transitions from n (its chromatic number) to n+1 exactly at s= n!; and χL((Kn∨C(2l+1)□K(1,s)) transitions from n+3 (its chromatic number) to n+4 at s=(1/3) (n+3)! (4l-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.
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)+a-1)(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, PL(G,k), the list analogue of the chromatic polynomial, that counts the number of different list colorings guaranteed for G with every k-list-assignment, 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 ≥ (PL(G, χL(G)+a-1))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 ≥ (PL(G, χL(G)+d-1))^a, then χL(G□H) ≥ χL(G)+d.
We show these bounds are sharp: if M is a strong k-chromatic choosable graph and k ≥ a+1, then χL(M□ K(a,b)) = χL(G)+a if and only if b ≥ (PL(M, χL(M)+a-1))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) = (PL(C(2l+1),4))2 = 9(9l-1)2; and f(Kn,a)= (PL(Kn, n+a-1))a = ((n+a-1)!/(a-1)!)a. We also prove a general lower bound on f(G,a) for strongly chromatic-choosable graphs.
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 k-list-assignment L of a graph G, proportional L-coloring of G is a proper L-coloring 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 k-choosable if a proportional L-coloring of G exists whenever L is a k-assignment for G.
We use matching theory to show that proportional choosability is monotonic in k, meaning that if G is proportionally k-choosable, then it must be proportionally (k+1)-choosable as well. We also show that proportional k-choosability is monotone, meaning that if H is a subgraph of G and G is proportionally k-choosable, then H is also proportionally k-choosable. 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 L-coloring with some additional restrictions into a proportional L-coloring for a k-assignment L of G with every color having multiplicity less than 2k, which helps us prove that any graph G is proportionally k-choosable 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.
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 2-choosable 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 2-choosable graphs is still open. Some intriguing questions about proportional choosability of paths are proposed.
Details forthcoming.
In the meantime, checkout Section 1 of the paper.
Details forthcoming.
In the meantime, checkout Sections 1 of the paper for a detailed overview.
We initiate the study of applying the Combinatorial Nullstellensatz to the DP-coloring of graphs even though, as is well-known, the Alon-Tarsi theorem does not apply to DP-coloring. The key obstacle to overcome in applying the Combinatorial Nullstellensatz to DP-coloring is: the graph polynomial is typically viewed as a polynomial over the reals which allows us only to prove results in the DP-coloring 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 S-labelings (a far-reaching generalization of many coloring problems such as signed colorings, DP-coloring, 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 DP-coloring. We apply these new tools along with the Quantitative Combinatorial Nullstellensatz to DP-coloring of the cones of certain bipartite graphs and uniquely 3-colorable graphs. We also extend a result of Akbari, Mirrokni, and Sadjad (2006) on unique list colorability to the context of DP-coloring. We establish a sufficient algebraic condition for a graph G to be 3-DP-colorable, 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 DP-chromatic number of the squares of all cycles.
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 DP-coloring (aka, correspondence coloring), a generalization of list coloring introduced by Dvorak and Postle in 2015, that has been studied extensively since then. Intuitively, DP-coloring considers the worst-case 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 t-chromatic 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 t-choice number of a graph G, denoted AL(G,t), the maximum number of vertices that can be properly colored for each t-list-assignment. The Partial List Coloring Conjecture, that is still open, states that for any graph G, AL(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 t-chromatic number, ADP(G,t), and extend this conjecture to DP-coloring.
We show that while the DP-coloring analogue of the Partial List Coloring Conjecture does not hold, several results on partial list coloring can be extended to the DP-coloring context. We call a graph partially DP-nice if it satisfies ADP(G,t) ≥ tn/χDP(G) for each t in {1, ...., χDP(G)}, where χDP(G) is the DP-chromatic number of G. We develop a new characterization of 2-fold covers and use it to construct several examples of graphs G with χDP(G)=3 and ADP(G,2) less than 2n/3, including an infinite family of graphs on 5k vertices, and the cube graph Q3. We show that the Wagner graph V8 is partially DP-nice, ADP(V8,2)=6, and that V8 has no induced subgraph with DP-chromatic number 2 and order at least (2/3)|V(V8)| which answers a natural open question about partial DP t-chromatic number of induced subgraphs.
We can conclude that every connected, subcubic, triangle-free graph, with the unique exception of Q3, is partially DP-nice. We use feedback vertex covers to observe that any nontrivial planar graph of girth at least 5 is partially DP-nice. We prove several more classes of graphs are partially DP-nice, including chordal graphs and series-parallel 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∨Kp is partially DP-nice.
We prove that ADP(G,t) ≥ n/ceiling[χDP(G)/t] for each t in {1, ...., χDP(G)}. It follows that for any graph G, the inequality ADP(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, ADP(G,t)) ≤ ∑i=1 to k(ADP(G,ti)) where t = ∑i=1 to k(ti).
DP-coloring (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, DP-coloring considers the worst-case 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 DP-chromatic 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 DP-chromatic 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 ≥ (PDP(G, χDP(G)+a-1))a. Recall that PDP(G,m) is the DP color function of a graph G, DP coloring analogue of the chromatic polynomial, which counts the minimum number of DP-colorings over all possible m-fold 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 DP-chromatic 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 twisted-canonical 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(C2m+2, 1) = PDP(C2m+2, 3) = 22m+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 twisted-canonical 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(Cm, k) of the form ck (PDP(Cm, k+2) / (k+2))k where the form of ck depends on the parity of the cycle. In particular we get that for any m, f(C2m+1, 1) = PDP(C2m+1, 3)/3 = (22m+1 - 2)/3.
Details forthcoming.
In the meantime, checkout Sections 1.3 and 1.4 of the paper.
Details forthcoming.
In the meantime, checkout Sections 1 of the paper for a detailed overview.
The chromatic polynomial of a graph G, P(G,m), counts the number of proper m-colorings of G. It was introduced by Birkhoff in 1912 to study the four-color problem, and is one the central objects in algebraic graph theory. The list color function of graph G, PL(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. DP-coloring (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, DP-coloring considers the worst-case 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 DP-coloring analogue of the chromatic polynomial called the DP color function, denoted PDP(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 PL(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 PDP(G,m) < P(G,m) when m is sufficiently large. We also study the asymptotics of P(G,m) - PDP(G,m) for a fixed graph G.
We use probabilistic arguments to prove a sharp lower bound on PDP(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 PDP(G,m) exactly and apply them to certain classes of graphs such as chordal graphs (where PDP(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 PDP(G∨Kp, m) = P(G∨Kp, m) for large enough m.
The chromatic polynomial of a graph G, P(G,m), counts the number of proper m-colorings of G. It was introduced by Birkhoff in 1912 to study the four-color problem, and is one the central objects in algebraic graph theory. The list color function of graph G, PL(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. DP-coloring (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, DP-coloring considers the worst-case 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 PDP(G,m), counts the minimum number of DP-colorings over all possible m-fold covers. It is known that from our previous work, unlike the list color function PL(G,m), for any g ≥ 3 there exists a graph, G, with girth g such that PDP(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 PDP(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 PDP(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 PDP(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 PDP(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 G1 and a spanning forest G0. The problem then reduces to carefully counting the number H0-colorings of G0 that are not H-colorings of G, where H0 is the m-fold cover of G0 induced by a given m-fold H of G.
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, PL(G,m), the list analogue of the chromatic polynomial, that counts the number of different list colorings guaranteed for G with every m-list-assignment. It follows that PL(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 PL(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 PL(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(K2,n) - χL(K2,n) ≥ c sqrt(n). We conjecture that this lower bound captures the behavior of t(K2,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 dmax(m) = max {t(G) - χL(G) : G is a graph with at most m edges} and tmax(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 c1 sqrt(m) ≤ dmax(m) ≤ c2 m for large enough m, and c3 sqrt(m) ≤ tmax(m) ≤c2 m for large enough m. We ask what is the asymptotic behavior of dmax(m) and tmax(m)? In particular, if tmax(m) grows faster than sqrt(m) then dmax(m) will be asymptotic to tmax(m).
DP-coloring (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 PDP(G,m), counts the minimum number of DP-colorings over all possible m-fold covers. Chromatic polynomials for clique-gluings 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 Kp-gluings of graphs. Recently, Becker et. al. asked whether PDP(G,m) ≤ (Πi=1 to n PDP(Gi,m))( Πi=0 to p-1 (m-i) )n-1 whenever m ≥ p, where the expression on the right is the DP-coloring analogue of the corresponding chromatic polynomial formula for a Kp-gluing of G1, ...., Gn. 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 (vertex-gluings). In this paper we show this inequality holds for edge-gluings (p=2). On the other hand, we show it does not hold for triangle-gluings (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 m-fold covers that we conjecture would yield the fewest DP-colorings for a given graph, of the inequality holds when p ≥ 3.
DP-coloring (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 PDP(G,m), counts the minimum number of DP-colorings over all possible m-fold covers. A function f is chromatic-adherent 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 chromatic-adherent, but there are only two known graphs that demonstrate this.
Suppose G is an n-vertex multigraph and H is a 3-fold 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 non-zeros of this polynomial equals the number of H-colorings of G. We then use a well-known result of Alon and Furedi on the number of non-zeros of a polynomial to establish a non-trivial and sharp lower bound 3n - l/2 on PDP(G,3) when 2n > l =|E(G)|. As an immediate application, consider a n-vertex 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 PDP(G,3) ≥ 3n/6. This bound gives a major improvement on the previously known bounds of Thomassen (2007) and Postle and Smith-Roberge (2022+) on both DP-color function and the list-color function of these graphs.
Finally, we use this bound to show that there are infinitely many graphs that demonstrate the non-chromatic-adherence of the DP color function.
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 n-vertex planar graph G, the chromatic polynomial satisfies P(G, k) ≥ k(k-1)(k-2)(k-3)(n-3) for all real numbers k ≥ 4. They proved this is true for k = 5, thus giving exponentially many 5-colorings of planar graphs. After Thomassen in 1994 proved all planar graphs are 5-choosable, there has been much work done on showing that planar graphs and their subfamilies have exponentially many list k-colorings 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 S-labeled 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 so-called 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.
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 L-packing of a graph G of size k is a set of k pairwise disjoint proper L-colorings 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 Pl*(G,q,k) as the guaranteed number of proper L-packings 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 Pl*(G,q)= Pl*(G,q,q) so that Pl*(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, Pl(G,q), is Pl*(G,q,1). Inspired by the well-known behavior of the list color function and the chromatic polynomial, we make progress towards the question of whether Pl*(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.
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 Pl(G, k) which is the guaranteed number of list colorings of a labeled graph G over all k-list assignments of G. In this paper, we extend Hanlon's definition to the list context and define the unlabeled list color function Pl(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 Pl(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 point-determining graphs (also known as irreducible graphs and as mating graphs). Point-determining 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 point-determining but satisfy this property.
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 color-preserving 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(Gd) ≤ χ(G)+1, where Gd 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.
We initiate the study of applying the Combinatorial Nullstellensatz to the DP-coloring of graphs even though, as is well-known, the Alon-Tarsi theorem does not apply to DP-coloring. The key obstacle to overcome in applying the Combinatorial Nullstellensatz to DP-coloring is: the graph polynomial is typically viewed as a polynomial over the reals which allows us only to prove results in the DP-coloring 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 S-labelings (a far-reaching generalization of many coloring problems such as signed colorings, DP-coloring, 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 DP-coloring. We apply these new tools along with the Quantitative Combinatorial Nullstellensatz to DP-coloring of the cones of certain bipartite graphs and uniquely 3-colorable graphs. We also extend a result of Akbari, Mirrokni, and Sadjad (2006) on unique list colorability to the context of DP-coloring. We establish a sufficient algebraic condition for a graph G to be 3-DP-colorable, 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 DP-chromatic number of the squares of all cycles.
Kneser graphs have been well-studied 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 G2 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 non-trivial problem arises when n=2k+1, that is the Odd graph. This remains an open problem and it is believed that the chromatic number χ(K2(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 χ(K2(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) + 2log2(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.
The chromatic polynomial of a graph G, P(G,m), counts the number of proper m-colorings of G. It was introduced by Birkhoff in 1912 to study the four-color problem, and is one the central objects in algebraic graph theory. The list color function of graph G, PL(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. DP-coloring (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, DP-coloring considers the worst-case 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 DP-coloring analogue of the chromatic polynomial called the DP color function, denoted PDP(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 PL(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 PDP(G,m) < P(G,m) when m is sufficiently large. We also study the asymptotics of P(G,m) - PDP(G,m) for a fixed graph G.
We use probabilistic arguments to prove a sharp lower bound on PDP(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 PDP(G,m) exactly and apply them to certain classes of graphs such as chordal graphs (where PDP(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 PDP(G∨Kp, m) = P(G∨Kp, m) for large enough m.
DP-coloring (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 PDP(G,m), counts the minimum number of DP-colorings over all possible m-fold covers. A function f is chromatic-adherent 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 chromatic-adherent, but there are only two known graphs that demonstrate this.
Suppose G is an n-vertex multigraph and H is a 3-fold 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 non-zeros of this polynomial equals the number of H-colorings of G. We then use a well-known result of Alon and Furedi on the number of non-zeros of a polynomial to establish a non-trivial and sharp lower bound 3n - l/2 on PDP(G,3) when 2n > l =|E(G)|. As an immediate application, consider a n-vertex 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 PDP(G,3) ≥ 3n/6. This bound gives a major improvement on the previously known bounds of Thomassen (2007) and Postle and Smith-Roberge (2022+) on both DP-color function and the list-color function of these graphs.
Finally, we use this bound to show that there are infinitely many graphs that demonstrate the non-chromatic-adherence of the DP color function.
Details forthcoming.
In the meantime, checkout Sections 1.3 and 1.4 of the paper.
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 n-vertex planar graph G, the chromatic polynomial satisfies P(G, k) ≥ k(k-1)(k-2)(k-3)(n-3) for all real numbers k ≥ 4. They proved this is true for k = 5, thus giving exponentially many 5-colorings of planar graphs. After Thomassen in 1994 proved all planar graphs are 5-choosable, there has been much work done on showing that planar graphs and their subfamilies have exponentially many list k-colorings 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 S-labeled 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 so-called 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.
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 L-packing of a graph G of size k is a set of k pairwise disjoint proper L-colorings 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 Pl*(G,q,k) as the guaranteed number of proper L-packings 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 Pl*(G,q)= Pl*(G,q,q) so that Pl*(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, Pl(G,q), is Pl*(G,q,1). Inspired by the well-known behavior of the list color function and the chromatic polynomial, we make progress towards the question of whether Pl*(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.
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 Pl(G, k) which is the guaranteed number of list colorings of a labeled graph G over all k-list assignments of G. In this paper, we extend Hanlon's definition to the list context and define the unlabeled list color function Pl(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 Pl(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 point-determining graphs (also known as irreducible graphs and as mating graphs). Point-determining 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 point-determining but satisfy this property.
I maintain a widely used list of Journals in discrete mathematics and related fields , which also give an indication of my research interests.
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 Pl(G, k) which is the guaranteed number of list colorings of a labeled graph G over all k-list assignments of G. In this paper, we extend Hanlon's definition to the list context and define the unlabeled list color function Pl(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 Pl(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 point-determining graphs (also known as irreducible graphs and as mating graphs). Point-determining 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 point-determining but satisfy this property.
Details forthcoming.
In the meantime, checkout Sections 1 of the paper for a detailed overview.
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 L-packing of a graph G of size k is a set of k pairwise disjoint proper L-colorings 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 Pl*(G,q,k) as the guaranteed number of proper L-packings 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 Pl*(G,q)= Pl*(G,q,q) so that Pl*(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, Pl(G,q), is Pl*(G,q,1). Inspired by the well-known behavior of the list color function and the chromatic polynomial, we make progress towards the question of whether Pl*(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.
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 n-vertex planar graph G, the chromatic polynomial satisfies P(G, k) ≥ k(k-1)(k-2)(k-3)(n-3) for all real numbers k ≥ 4. They proved this is true for k = 5, thus giving exponentially many 5-colorings of planar graphs. After Thomassen in 1994 proved all planar graphs are 5-choosable, there has been much work done on showing that planar graphs and their subfamilies have exponentially many list k-colorings 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 S-labeled 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 so-called 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.
Details forthcoming.
In the meantime, checkout Sections 1.3 and 1.4 of the paper.
Details forthcoming.
In the meantime, checkout Section 1.3 of the paper.
Details forthcoming.
In the meantime, checkout Section 1 of the paper.
DP-coloring (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 PDP(G,m), counts the minimum number of DP-colorings over all possible m-fold covers. A function f is chromatic-adherent 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 chromatic-adherent, but there are only two known graphs that demonstrate this.
Suppose G is an n-vertex multigraph and H is a 3-fold 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 non-zeros of this polynomial equals the number of H-colorings of G. We then use a well-known result of Alon and Furedi on the number of non-zeros of a polynomial to establish a non-trivial and sharp lower bound 3n - l/2 on PDP(G,3) when 2n > l =|E(G)|. As an immediate application, consider a n-vertex 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 PDP(G,3) ≥ 3n/6. This bound gives a major improvement on the previously known bounds of Thomassen (2007) and Postle and Smith-Roberge (2022+) on both DP-color function and the list-color function of these graphs.
Finally, we use this bound to show that there are infinitely many graphs that demonstrate the non-chromatic-adherence of the DP color function.
DP-coloring (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 PDP(G,m), counts the minimum number of DP-colorings over all possible m-fold covers. Chromatic polynomials for clique-gluings 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 Kp-gluings of graphs. Recently, Becker et. al. asked whether PDP(G,m) ≤ (Πi=1 to n PDP(Gi,m))( Πi=0 to p-1 (m-i) )n-1 whenever m ≥ p, where the expression on the right is the DP-coloring analogue of the corresponding chromatic polynomial formula for a Kp-gluing of G1, ...., Gn. 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 (vertex-gluings). In this paper we show this inequality holds for edge-gluings (p=2). On the other hand, we show it does not hold for triangle-gluings (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 m-fold covers that we conjecture would yield the fewest DP-colorings for a given graph, of the inequality holds when p ≥ 3.
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 in-depth 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 NP-hard on arbitrary graphs become polynomial on outerplanar graphs. An in-depth 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 NP-hard. Hence, instead of solving the problem exactly, we develop polynomial-time 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 non-trivial 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 4-cycles 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 4-cycles would not improve the approximation ratio.
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, PL(G,m), the list analogue of the chromatic polynomial, that counts the number of different list colorings guaranteed for G with every m-list-assignment. It follows that PL(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 PL(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 PL(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(K2,n) - χL(K2,n) ≥ c sqrt(n). We conjecture that this lower bound captures the behavior of t(K2,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 dmax(m) = max {t(G) - χL(G) : G is a graph with at most m edges} and tmax(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 c1 sqrt(m) ≤ dmax(m) ≤ c2 m for large enough m, and c3 sqrt(m) ≤ tmax(m) ≤c2 m for large enough m. We ask what is the asymptotic behavior of dmax(m) and tmax(m)? In particular, if tmax(m) grows faster than sqrt(m) then dmax(m) will be asymptotic to tmax(m).
The chromatic polynomial of a graph G, P(G,m), counts the number of proper m-colorings of G. It was introduced by Birkhoff in 1912 to study the four-color problem, and is one the central objects in algebraic graph theory. The list color function of graph G, PL(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. DP-coloring (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, DP-coloring considers the worst-case 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 PDP(G,m), counts the minimum number of DP-colorings over all possible m-fold covers. It is known that from our previous work, unlike the list color function PL(G,m), for any g ≥ 3 there exists a graph, G, with girth g such that PDP(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 PDP(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 PDP(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 PDP(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 PDP(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 G1 and a spanning forest G0. The problem then reduces to carefully counting the number H0-colorings of G0 that are not H-colorings of G, where H0 is the m-fold cover of G0 induced by a given m-fold H of G.
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, PL(G,m), the list analogue of the chromatic polynomial, that counts the number of different list colorings guaranteed for G with every m-list-assignment. It follows that PL(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 PL(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 PL(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(K2,n) ≥ c sqrt(n), and it was conjectured that this lower bound captures the behavior of t(K2,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(K2,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 enumerative-chromatic choosability of K2,n.
We offer a general approach to modeling longitudinal network data, including exponential random graph models (ERGMs), that vary according to certain discrete-time Markov chains. We connect conditional and Markovian exponential families, permutation-uniform 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 closed-form expressions for maximum likelihood estimators. We also introduce exponential random t-multigraph models, motivated by our result on replacing t observations of permutation-uniform Markov chains of graphs with single observations of corresponding multigraphs.
DP-coloring (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, DP-coloring considers the worst-case 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 DP-chromatic 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 DP-chromatic 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 ≥ (PDP(G, χDP(G)+a-1))a. Recall that PDP(G,m) is the DP color function of a graph G, DP coloring analogue of the chromatic polynomial, which counts the minimum number of DP-colorings over all possible m-fold 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 DP-chromatic 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 twisted-canonical 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(C2m+2, 1) = PDP(C2m+2, 3) = 22m+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 twisted-canonical 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(Cm, k) of the form ck (PDP(Cm, k+2) / (k+2))k where the form of ck depends on the parity of the cycle. In particular we get that for any m, f(C2m+1, 1) = PDP(C2m+1, 3)/3 = (22m+1 - 2)/3.
DP-coloring (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 m-colorings of graph G. Counting function analogues of the chromatic polynomial have been introduced and studied for list colorings: PL, the list color function (1990); DP colorings: PDP, the DP color function (2019), and PDP*, the dual DP color function (2021). For any graph G and m, PDP(G, m) ≤ PL(G,m) ≤ P(G,m) ≤ PDP*(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 chromatic-adherent 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 chromatic-adherent. We show that the DP color function is not chromatic-adherent 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.
We prove a common generalization of the celebrated Sauer-Spencer 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 c-degenerate graph, both on n vertices, with degree sequences (g1, ..., gn) and (h1, ..., hn) in non-increasing order, respectively. If ∑i=1 to D(hi) + ∑i=1 to c(gi) < 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 (n-1) 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.
We consider a linear relaxation of a generalized minimum-cost 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 well-known 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.
DP-coloring (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 PDP(G,m), counts the minimum number of DP-colorings over all possible m-fold covers. Chromatic polynomials for joins and vertex-gluings 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 vertex-gluings of certain graphs. We also develop tools to study the DP color function under these graph operations, such as: given vertex disjoint graphs G1, .... Gn, we define amalgamated cover, a natural analogue of "gluing" m-fold covers of each Gi together so that we get an m-fold cover for any G formed by vertex gluing the graphs G1, .... Gn; and we define separated covers, a natural analogue of "splitting" an m-fold cover of any G formed by clique-gluing the graphs G1, .... Gn into separate m-fold 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.
Equitable k-choosability is a list analogue of equitable k-coloring 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 k-choosable, the disjoint union of G and H may not be equitably k-choosable. Also, unlike many other variants of list coloring problems, a complete characterization of equitably 2-choosable graphs is not known, and in general not much is known about equitable k-choosability 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 NP-complete 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 2-choosable. This makes progress on the task of identifying which graphs are equitably 2-choosable, and also shows that there are only 14 equitably 2-choosable graphs (up to isomorphism) that are the disjoint union of two stars, unlike the infinitely many equitably 2-colorable graphs that are the disjoint union of two stars. We completely determine when the disjoint union of n identical stars is equitably 2-choosable, 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 k-choosability of two stars for arbitrary k.
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 optimization-based 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.
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 k-list 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 k-list 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 G-S 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 k-list 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, 2-degenerate graphs, and certain other graphs.
We use probabilistic and algorithmic arguments to show that if G is equitably k-list arborable it does not necessarily follow that G is equitably (k+1)-list arborable which addresses a question of Drgas-Burchardt et al. (2018). We also show that it is not necessary that if a graph G is equitably k-list arborable then G is also equitably vertex k-arborable.
The chromatic polynomial of a graph G, P(G,m), counts the number of proper m-colorings of G. It was introduced by Birkhoff in 1912 to study the four-color problem, and is one the central objects in algebraic graph theory. The list color function of graph G, PL(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. DP-coloring (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, DP-coloring considers the worst-case 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 DP-coloring analogue of the chromatic polynomial called the DP color function, denoted PDP(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 PL(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 PDP(G,m) < P(G,m) when m is sufficiently large. We also study the asymptotics of P(G,m) - PDP(G,m) for a fixed graph G.
We use probabilistic arguments to prove a sharp lower bound on PDP(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 PDP(G,m) exactly and apply them to certain classes of graphs such as chordal graphs (where PDP(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 PDP(G∨Kp, m) = P(G∨Kp, m) for large enough m.
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 DP-coloring (aka, correspondence coloring), a generalization of list coloring introduced by Dvorak and Postle in 2015, that has been studied extensively since then. Intuitively, DP-coloring considers the worst-case 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 t-chromatic 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 t-choice number of a graph G, denoted AL(G,t), the maximum number of vertices that can be properly colored for each t-list-assignment. The Partial List Coloring Conjecture, that is still open, states that for any graph G, AL(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 t-chromatic number, ADP(G,t), and extend this conjecture to DP-coloring.
We show that while the DP-coloring analogue of the Partial List Coloring Conjecture does not hold, several results on partial list coloring can be extended to the DP-coloring context. We call a graph partially DP-nice if it satisfies ADP(G,t) ≥ tn/χDP(G) for each t in {1, ...., χDP(G)}, where χDP(G) is the DP-chromatic number of G. We develop a new characterization of 2-fold covers and use it to construct several examples of graphs G with χDP(G)=3 and ADP(G,2) less than 2n/3, including an infinite family of graphs on 5k vertices, and the cube graph Q3. We show that the Wagner graph V8 is partially DP-nice, ADP(V8,2)=6, and that V8 has no induced subgraph with DP-chromatic number 2 and order at least (2/3)|V(V8)| which answers a natural open question about partial DP t-chromatic number of induced subgraphs.
We can conclude that every connected, subcubic, triangle-free graph, with the unique exception of Q3, is partially DP-nice. We use feedback vertex covers to observe that any nontrivial planar graph of girth at least 5 is partially DP-nice. We prove several more classes of graphs are partially DP-nice, including chordal graphs and series-parallel 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∨Kp is partially DP-nice.
We prove that ADP(G,t) ≥ n/ceiling[χDP(G)/t] for each t in {1, ...., χDP(G)}. It follows that for any graph G, the inequality ADP(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, ADP(G,t)) ≤ ∑i=1 to k(ADP(G,ti)) where t = ∑i=1 to k(ti).
We introduce a notion of color-criticality in the context of chromatic-choosability, χ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 k-chromatic-choosable if χ(G)=k and every (k-1)-list-assignment for which G is not list-colorable 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 list-coloring. We prove basic properties of strongly chromatic-choosable graphs such as chromatic-choosability and vertex-criticality, and we construct infinite families of strongly chromatic-choosable 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 chromatic-choosable graphs and use it to show that: if M is a strong k-chromatic-choosable graph with |E(M)| at most |V(M)|(k-2) 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, PL(G,k), the list analogue of the chromatic polynomial, that counts the number of different list colorings guaranteed for G with every k-list-assignment. The sharpness examples are constructed recursively as: S(M,B',r) that glues together PL(M,k+r-2) disjoint copies of S(M,B',r-1), starting with S(M,B',1)=B', a subdivision of a star with PL(M,k)-1 leaves. This gives us recursive constructions of large chromatic-choosable graphs.
We use the list color function to determine the list chromatic number of certain star-like graphs, here K(1,s) is the star with s leaves: χL(M□K(1,s)) = k if s < PL(M,k), or k+1 if s ≥ PL(M,k), where M is any strong k-chromatic-choosable graph. We use the results that PL(M,k)=P(M,k) when M is an odd cycle (C(2l+1)), complete graph (Kn), 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(Kn□K(1,s)) transitions from n (its chromatic number) to n+1 exactly at s= n!; and χL((Kn∨C(2l+1)□K(1,s)) transitions from n+3 (its chromatic number) to n+4 at s=(1/3) (n+3)! (4l-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.
Kneser graphs have been well-studied 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 G2 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 non-trivial problem arises when n=2k+1, that is the Odd graph. This remains an open problem and it is believed that the chromatic number χ(K2(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 χ(K2(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) + 2log2(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.
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 2-choosable 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 2-choosable graphs is still open. Some intriguing questions about proportional choosability of paths are proposed.
We initiate the study of applying the Combinatorial Nullstellensatz to the DP-coloring of graphs even though, as is well-known, the Alon-Tarsi theorem does not apply to DP-coloring. The key obstacle to overcome in applying the Combinatorial Nullstellensatz to DP-coloring is: the graph polynomial is typically viewed as a polynomial over the reals which allows us only to prove results in the DP-coloring 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 S-labelings (a far-reaching generalization of many coloring problems such as signed colorings, DP-coloring, 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 DP-coloring. We apply these new tools along with the Quantitative Combinatorial Nullstellensatz to DP-coloring of the cones of certain bipartite graphs and uniquely 3-colorable graphs. We also extend a result of Akbari, Mirrokni, and Sadjad (2006) on unique list colorability to the context of DP-coloring. We establish a sufficient algebraic condition for a graph G to be 3-DP-colorable, 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 DP-chromatic number of the squares of all cycles.