Papers and Publications

My recent papers in reverse-chronological order are available through here, while below my papers are grouped under their primary topics.

Most of my papers are also accessible through my Google Scholar page
See the bottom of the page for some for Talk Slides.


In the list below, ^ indicates a co-author who was a student at the time of writing the paper.
Recent papers are marked with new! or updated! below.

Book

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

Papers on Optimization, Algorithms, Operations Research, and Mathematical Modeling

• Global Optima Results for the Kauffman NK Model, (with S.H. Jacobson), Mathematical Programming, Volume 106, 2006, 319-338.
  summary:

  The Kauffman NK model is a stochastic combinatorial optimization model that has been used in theoretical biology, physics and management science to model complex systems with interacting components. It could be crudely described as an optimization problem to find a maximum valued (weighted) 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



• New Global Optima Results for the Kauffman NK Model: Handling Dependency, (with S.H. Jacobson), Mathematical Programming, Special issue on 'Optimization under Uncertainty', Volume 108, 2006, 475-494.
  summary:

  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).



• Analyzing the Performance of Simultaneous Generalized Hill Climbing Algorithms, (with D.E. Vaughan and S.H. Jacobson), Computational Optimization and Applications, Volume 37, 2007, 103-119.
  summary:

  Simultaneous generalized hill climbing (SGHC) algorithms provide a framework for using heuristics to simultaneously address sets of intractable discrete optimization problems where information is shared between the problems during the algorithm execution. A SGHC algorithm probabilistically moves between discrete optimization problems during its execution according to a (problem generation) probability function. Many well-known heuristics (Generalized Hill Climbing (GHC) algorithms), including simulated annealing, threshold accepting and pure local search, can be embedded within the SGHC algorithm framework.
  
  This paper shows that the solutions generated by an SGHC algorithm are a stochastic process that satisfies the Markov property. This allows the problem probability mass functions to be formulated for particular sets of problems based on the long-term behavior of the algorithm. Such results can be used to determine the proportion of iterations that an SGHC algorithm will spend optimizing over each discrete optimization problem. Sufficient conditions that guarantee that the algorithm spends an equal number of iterations in each discrete optimization problem are provided. SGHC algorithms can also be formulated such that the overall performance of the algorithm is independent of the initial discrete optimization problem chosen. Sufficient conditions are obtained guaranteeing that an SGHC algorithm will visit the globally optimal solution for each discrete optimization problem. Lastly, rates of convergence for SGHC algorithms are reported that show that given a rate of convergence for the embedded GHC algorithm, the SGHC algorithm can be designed to preserve this rate.



• Long Local Searches for Maximal Bipartite Subgraphs, (with D.B. West), SIAM Journal on Discrete Mathematics, Volume 22, 2008, 1138-1144.
  summary:

  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)n². Note that (1/4)n² is a trivial upper bound. We also prove better upper bounds like [|E(G)|-(1/4)d²], in terms of d the minimum degree of the graph. We also show that the minimum number of flips needed to reach a global optimum ≤ n/2, answering a question of Cowen and West.



• Reductions for the Stable Set Problem, (with E.C. Sewell and S.H. Jacobson), Algorithmic Operations Research, Vol 6(1), 2011, 40-55.
  summary:

  One approach to finding a maximum stable (independent) set (MSS) (or, equivalently a maximum clique or a minimum vertex cover) in a graph is to try to reduce the size of the problem by transforming the problem into an equivalent problem on a smaller graph. These reductions have been used to study properties of stability critical graphs and facets of the stable set polytope. They have also been used algorithmically in heuristics, polynomial-time algorithms for special classes of graphs, and exact algorithms.
  
  This paper introduces several new reductions for the MSS problem, extends several well known reductions to the maximum weight stable set (MWSS) problem, demonstrates how reductions for the generalized stable set problem can be used in conjunction with probing to produce powerful new reductions for both the MSS and MWSS problems, and shows how hypergraphs can be used to expand the capabilities of clique projections. The effectiveness of these new reduction techniques are illustrated on a set of challenging MSS problems arising from Steiner Triple Systems.



• Maximum Series-Parallel Subgraph: Approximation Algorithms, (with G. Calinescu and C.G. Fernandes), Algorithmica, Vol 63, 2012, 137-157.
  A refereed conference version in: Graph-Theoretic Concepts in Computer Science 2009, Lecture Notes in Computer Science, Volume 5911, 2010, 54-65.
  summary:

  Consider the NP-hard problem of, given a simple graph G, to find a K₄-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.



• Approximating the Quadratic Knapsack Problem and its Generalization, (with S. Kapoor and M. Pelsmajer), technical report.
  summary:

  We consider a reformulation of the Quadratic Knapsack Problem, the Graph Knapsack Problem where a given graph G (and similarly its generalization, the Hypergraph Knapsack Problem with an underlying hypergraph) has weights on vertices and benefits on edges and vertices. Given a budget bound W the goal is to identify a subset of vertices having total weight at most W such that the benefit of the induced subgraph (similarly, subhypergraph) is maximized. These problems generalize many graph optimization problems and other generalizations of the Knapsack problem such as Knapsack Problem with Conflict Graph, Constrained Knapsack Problem, Precedence-Constrained Knapsack Problem, and Subset-Union Knapsack Problem, which are all NP-hard and most are even hard to approximate. In particular they generalize the Quadratic Knapsack Problem as well as the dense k-subgraph problem and arise naturally in the context of resource allocation in transportation systems.
  
  We give examples that show that algorithms proposed for Classical Knapsack problem and the Heaviest subgraph problem behave poorly when applied to GKP. We give a FPTAS (Fully Polynomial Time Approximation Scheme) when the underlying graph has bounded Tree-width. We can also generalize this result to the Hypergraph version of the GKP, where the dependencies between items are not just pairwise but k-wise for any k ≥ 2.



• New Methodology for Transportation Investment Decisions with Consideration of Project Interdependencies, (with Z. Li, S. Kapoor, and E. Veliou^, B. Zhou^, C. Lee^), Transportation Research Record: Journal of the Transportation Research Board of the National Academies, Issue 2285, 2012, 36-46.
  summary:

  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.



• Approximating 0-1 Quadratic Programming using Second Order Cone Programs, (with S. Kapoor), technical report.
  summary:

  We consider the problem of approximating Quadratic 0-1 Integer Programs with non-negative integer constraint matrix entries, which we term as PIQP. Our approximation is based on a program with hyperbolic constraints (a Second-Order Cone Programming -SOCP- formulation) that achieves an approximation ratio of O(a(max) (n/b(n))), where a(max) is the maximum size of an entry in the constraint matrix defined by constraints a_i^TX ≤ W_i, for all i, and b(n) ≤ max{W_i}. By appropriately choosing b(n), the randomized algorithm, when combined with other algorithms that achieve good approximations for larger values of b(n), allows better algorithms for the complete range of W_i. Our solution is achieved by a randomization of the optimal solution to the relaxed version of the hyperbolic program. We show that this solution provides the approximation bounds using non-linear concentration of measure bounds studied by Kim and Vu. The bounds achieved, together with a greedy algorithm, provide a O*(a(max) n^1/2) factor approximation, where O* hides logarithmic terms.



• updated! A Linear Input Dependence Model for Interdependent Networks, (with A. Rumpf^), European Journal of Operational Research, Volume 302, 2022, 781-797.
  summary:

  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.



• updated! A Public Transit Network Optimization Model for Equitable Access to Social Services, (with A. Rumpf^), refereed conference version in ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization 2021 (EAAMO '21), Article 16, 2021, 1-17..
  summary:

  The primary focus of this paper is to consider a problem which is in some ways the inverse of the classical facility location problem: rather than changing facility locations in a fixed transit network, we consider changing a transit network containing fixed facility locations. This can improve accessibility levels in the same way that placing facilities can, since reducing travel times makes effective catchment areas larger and brings fast access to more communities. Public transit planning can also be implemented much more immediately since tactical decisions like bus frequency setting can be enacted without the need for permanent changes to the infrastructure.
  
  We present a flexible public transit network design model which optimizes a social access objective while guaranteeing that the system’s costs and transit times remain within a preset margin of their current levels. The purpose of the model is to find a set of minor, immediate modifications to an existing bus network that can give more communities access to the chosen social services while having a minimal impact on the current network’s operator costs and user costs. Design decisions consist of reallocation of existing resources in order to adjust line frequencies and capacities. We present a hybrid tabu search/simulated annealing algorithm for the solution of this 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.



• updated! Longitudinal network models and permutation-uniform Markov chains, (with W. Schwartz^, and S. Petrovic), Scandinavian Journal of Statistics, to appear, In press (2022).
  summary:

  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.



• updated! An Improved Algorithm for Finding Maximum Outerplanar Subgraphs, (with Gruia Calinescu, and Bahareh Kudarzi^), Discrete Applied Mathematics, accepted for publication.
  summary:

  Given a graph G, finding an outerplanar subgraph of G with the maximum number of edges is called the Maximum Outerplanar Subgraph problem. While outerplanar graphs have been investigated 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.

Papers on Graph Packing

• Extremal Graphs for a Graph Packing Theorem of Sauer and Spencer, (with A. Kostochka), Combinatorics, Probability and Computing, Volume 16, 2007, 409-417.
  summary:

  Let G, H be graphs with maximum degrees D(G), D(H), and orders n(G), n(H) at most n. G and H are said to pack if there exist injective mappings of the vertex sets into [n], such that the images of the edge sets do not intersect. In other words, either G or H is isomorphic to a subgraph of the complement of the other. The concept of graph packing generalizes various extremal graph problems, including problems on existence of fixed subgraphs (such as the Hamiltonian Cycle problem), forbidden subgraphs (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).



• On a Graph Packing Conjecture of Bollobas, Eldridge, and Catlin, (with A. Kostochka and G.Yu), Combinatorica, Volume 28, 2008, 469-485.
  summary:

  See the definition of graph packing and related notation in the summary above. One of the earliest results in this area was by Sauer and Spencer (1978) : if 2D(G)D(H) < n then G and H pack. The main conjecture in the area was made by Bollobas and Eldridge in 1978, and independently by Catlin in 1974, as an extension of the 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.



• Packing of Graphic n-tuples, (with A. Busch, M. Ferrara, S. Hartke, M.S. Jacobson, and D.B. West), Journal of Graph Theory, Vol 70, 2012, 29-39.
  summary:

  Let p=(p₁,...,p_n) and q=(q₁,...,q_n) 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 v₁, ..., v_n such that the degrees of v_i in G and H are p_i and q_i, respectively. When packing graphs, we permit permuting the vertices to make G and H "fit together", but when packing sequences, we do not permit the sequences to be permuted. From an optimization 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.



• updated! A Generalization of the Graph Packing Theorems of Sauer-Spencer and Brandt, (with B. Reiniger), Combinatorica, 42 (2022), 1347–1356.
  summary:

  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 (g₁, ..., g_n) and (h₁, ..., h_n) in non-increasing order, respectively. If ∑_{i=1 to D}(h_i) + ∑_{i=1 to c}(g_i) < n then G and H pack.
  
  This proof leads to the characterization of the extremal graphs in the case of Brandt's theorem: If G is a graph of maximum degree D, and F is a forest, both on n vertices, and 3D+l*(F) ≤ n, then G and F pack, unless n is even, G is a perfect matching, and F is a star with (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.

Papers on Graph Coloring, its variants, and applications

• See above for an application of equitable coloring of the dependency graph of random variables as a means to study their order statistics in:
  New Global Optima Results for the Kauffman NK Model: Handling Dependency, (with S.H. Jacobson), Mathematical Programming, Special issue on 'Optimization under Uncertainty', Volume 108, 2006, 475-494.


• Distinguishing Chromatic Number of Cartesian Products of Graphs, (with J. Choi^ and S. Hartke), SIAM Journal on Discrete Mathematics, Volume 24, 2010, 82-100.
  summary:

  The distinguishing chromatic number of a graph G, χ_D(G), is the least number of colors needed for a proper coloring of G with the property that the only 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(G^d) ≤ χ(G)+1, where G^d denotes the Cartesian product of d copies of G. Using our proof techniques, we also find the distinguishing chromatic number for Hypercubes, Hamming graphs (Cartesian products of complete graphs), and Cartesian products of complete multipartite graphs.



• Guarding Orthogonal Art Galleries with Holes, (with Y. Jo^), technical report.
  summary:

  The original art gallery problem (V. Klee, 1973) asked for the minimum number of guards sufficient to see every point of the interior of an 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.



• On Graph Fall-Coloring - Existence and Constructions, (with C. Mitillos^), Graphs and Combinatorics, 35 (2019), 1633-1646.
  summary:

  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.



• On Graph Fall-Coloring - Operators and Heredity, (with C. Mitillos^), Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 106 (2018), 125-151.
  summary:

  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. Since a fall coloring of a graph need not always exist, the question of its existence is a fundamental problem.
  
  We study the effect that various graph operators have on fall-colorability. We consider binary graph operators such as the Cartesian, categorical, rooted, strong, and lexicographic products of graphs, as well as the graph join operation. We also study unary graph operators such as the power operators and the related middle and total graph operators, and the generalized Mycielski operators. We apply our results to prove a part of the Erdos-Faber-Lovasz conjecture, as well as reformulate the conjecture in terms of fall-coloring and hypergraphs. We define and study the notion of edit distance of graph to a fall-colorable supergraph using the edge insertion operator, and show that this is an NP-complete problem.
  
  We see the full spectrum of effects that these graph operators have on fall-colorability.
  Preservation of the fall colorability of the input graphs: the Cartesian, rooted, and categorical products.
  Modification of the fall colorability: the strong and lexicographic products, the join, and some of the generalized Mycielski operators.
  Elimination of the fall colorability: the usual Mycielski operator, as well as repeated applications of the Middle graph operator.
  Creation of fall colorability when applied to specific non-fall-colorable graphs: certain power operators, Cartesian power, or by edge insertion.



• A Note on the Chromatic Number of the Square of Kneser Graph K(2k+1,k), (with JH. Kang), Discrete Mathematics, 343 (2020), article 111630.
  summary:

  Kneser graphs have been 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 G² 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 χ(K²(2k+1,k)) = 2k+c where c is a constant. The best known upper bounds are by Kim and Park: (8k/3) + (20/3) for k ≥ 3 (2014) and (32k/15) + 32 for k ≥ 7 (2016). Kim and Park conjecture that χ(K²(2k+1,k)) ≤ 2k + 2 for all k large enough.
  
  We employ graph homomorphisms, Cartesian products of graphs, and linear congruences integrated with combinatorial arguments to prove an upper bound: 2(k+1) + 2log₂(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.



• new! Flexible list colorings: Maximizing the number of requests satisfied, (with R. Mathew, J. Mudrock, M. Pelsmajer), submitted for publication.
  summary:

  Details forthcoming.
  In the meantime, checkout Section 1 of the paper.

Papers on List Coloring of Graphs and its variants

Choosability and Counting Problems


• On Alon-Tarsi Number and Chromatic-choosability of Cartesian Products of Graphs, (with J. Mudrock^), The Elect. Journal of Combinatorics, 26 (2019), article P1.3.
  summary:

  We study the list chromatic number of Cartesian products of graphs through the 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.



• updated! Criticality, The List Color Function, and List Coloring the Cartesian Product of Graphs, (with J. Mudrock^), Journal of Combinatorics, Volume 12 (2021), 479-514.
  summary:

  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, P_L(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 P_L(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 P_L(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 < P_L(M,k), or k+1 if s ≥ P_L(M,k), where M is any strong k-chromatic-choosable graph. We use the results that P_L(M,k)=P(M,k) when M is an odd cycle (C_(2l+1)), complete graph (K_n), or the join of an odd cycle with a complete graph to prove:
  χ_L(C_(2l+1)□K_(1,s)) transitions from 3 (its chromatic number) to 4 at exactly s= 2^(2l+1)-2; χ_L(K_n□K_(1,s)) transitions from n (its chromatic number) to n+1 exactly at s= n!; and χ_L((K_n∨C_(2l+1)□K_(1,s)) transitions from n+3 (its chromatic number) to n+4 at s=(1/3) (n+3)! (4^l-1). We can extend this result to get chromatic choosability when the second factor is a subdivision of a star or an appropriately bounded rooted tree.



• List Coloring a Cartesian Product with a Complete Bipartite Factor, (with J. Mudrock), Graphs and Combinatorics, 35 (2019), 1571-1583.
  summary:

  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, P_L(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 ≥ (P_L(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 ≥ (P_L(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 ≥ (P_L(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) = (P_L(C_(2l+1),4))² = 9(9^l-1)²; and f(K_n,a)= (P_L(K_n, 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.



• updated! On the List Color Function Threshold, (with A. Kumar^, J. Mudrock, P. Rewers^, P. Shin^, K. To^), Journal of Graph Theory, accepted for publication.
  summary:

  In 1912 Birkhoff introduced the notion of the chromatic polynomial P(G,m), which counts the number of proper colorings with m colors in a graph G. The notion of chromatic polynomial was extended to list coloring in the early 1990s by Kostochka and Sidorenko. The list color function, P_L(G,m), the list analogue of the chromatic polynomial, that counts the number of different list colorings guaranteed for G with every m-list-assignment. It follows that P_L(G,m) ≤ P(G,m). In general, the list color function can differ significantly from the chromatic polynomial for small values of m. In 1992, Donner showed that for any graph G there is a k such that P_L(G,m) = P(G,m) whenever m ≥ k. The list color function threshold of G, denoted t(G) is the smallest k ≥ χ(G) such that P_L(G,m) = P(G,m) whenever m ≥ k. In 2009, Thomassen showed that for any graph G, t(G) ≤ |V(G)|¹⁰ + 1. Then, in 2017, Wang, Qian, and Yan significantly improved it to t(G) ≤ (1.14) |E(G)|.
  
  In 2009, Thomassen asked whether there a universal constant C such that for any graph G, t(G) ≤ χ_L(G) + C? We show that the answer to this question is no in a fairly strong sense by proving that there is a constant c such that for each l ≥ 16, t(K_2,n) - χ_L(K_2,n) ≥ c sqrt(n). We conjecture that this lower bound captures the behavior of t(K_2,n).
  
  In light of the bound of Wang, Qian, and Yan, Thomassen's Question, and our Theorem, it is natural to study the asymptotic behavior of the list color function threshold as the size of the graphs we consider tends toward infinity. We define the extremal functions d_max(m) = max {t(G) - χ_L(G) : G is a graph with at most m edges} and t_max(m) = max {t(G) : G is a graph with at most m edges}. By our Theorem and the bound of Wang, Qian, and Yan, we know that there exist constants such that c₁ sqrt(m) ≤ d_max(m) ≤ c₂ m for large enough m, and c₃ sqrt(m) ≤ t_max(m) ≤c₂ m for large enough m. We ask what is the asymptotic behavior of d_max(m) and t_max(m)? In particular, if t_max(m) grows faster than sqrt(m) then d_max(m) will be asymptotic to t_max(m).



• new! Bounding the List Color Function Threshold from Above, (with A. Kumar^, A. Liu^, J. Mudrock, P. Rewers^, P. Shin^, M.S. Tanahara^, K. To^), Involve: A journal of mathematics, accepted for publication.
  summary:

  In 1912 Birkhoff introduced the notion of the chromatic polynomial P(G,m), which counts the number of proper colorings with m colors in a graph G. The notion of chromatic polynomial was extended to list coloring in the early 1990s by Kostochka and Sidorenko. The list color function, P_L(G,m), the list analogue of the chromatic polynomial, that counts the number of different list colorings guaranteed for G with every m-list-assignment. It follows that P_L(G,m) ≤ P(G,m). In general, the list color function can differ significantly from the chromatic polynomial for small values of m. In 1992, Donner showed that for any graph G there is a k such that P_L(G,m) = P(G,m) whenever m ≥ k. The list color function threshold of G, denoted t(G) is the smallest k ≥ χ(G) such that P_L(G,m) = P(G,m) whenever m ≥ k. In 2009, Thomassen showed that for any graph G, t(G) ≤ |V(G)|¹⁰ + 1. Then, in 2017, Wang, Qian, and Yan significantly improved it to t(G) ≤ (1.14) |E(G)|.
  
  In an earlier work, it was proved that there is a positive constant c such that for each l ≥ 16, t(K_2,n) ≥ c sqrt(n), and it was conjectured that this lower bound captures the behavior of t(K_2,n). In this paper we develop tools for bounding the list color function threshold of complete bipartite graphs from above. We show that for any n, t(K_2,n) ≤ (n + 2.05)/1.24. Interestingly, our proof makes use of classical results from Analysis such as Rolle’s Theorem and Descartes’ Rule of Signs. We also ask questions and prove some results regarding enumerative-chromatic choosability of K_2,n.

Equitable Choosability Problems


• Total Equitable Choosability of Graphs, (with J. Mudrock^, M. Pelsmajer), Graphs and Combinatorics, 34 (2019), 1637-1649.
  summary:

  An equitable coloring is a proper coloring of a graph such that the sizes of the color classes differ by at most one. In 1994, Fu conjectured that for any simple graph G, the total graph of G, T(G), is equitably k-colorable whenever k ≥ max{χ(T(G)), D+2}, where χ(T(G)) is the chromatic number of the total graph of G and D is the maximum degree of G. Recall that vertex coloring of T(G) is the simultaneous proper coloring of vertices and edges of G.
  
  We investigate the list coloring analogue, as introduced by Kostochka, Pelsmajer, and West (2003), which prescribes an upper bound on the size of each color class in the list coloring. A graph is equitably k-choosable if it has a proper list coloring whenever vertices have lists of size k, where each color is used on at most |V(G)|/k vertices. In the spirit of Fu's conjecture, we conjecture that for any simple graph G, T(G) is equitably k-choosable whenever k ≥ max{χ_L(T(G)), D+2} where χ_L(T(G)) is the list chromatic number of T(G).
  
  We first prove sharp results on equitable choosability of all powers of paths and cycles, verifying the conjecture and more for these graphs. Our main result is the proof of this conjecture for all graphs satisfying D ≤ 2. Note that, it isn't enough to prove equitable k-choosability for every component of a graph. The disconnected case of the proof of our theorem requires development of new a list decomposition tool that should prove useful for other problems in equitable k-choosability of graphs. In fact, we prove equitable 4-choosability for graphs where components may be square of any path, square of any cycle on at least 6 vertices, or a copy of K₄, and we also prove equitable 3-choosability for graphs where each component is a square of a cycle of length divisible by 3 or a square of a path. So we find exactly which total graphs T(G) with D=2 are equitably 3-choosable.



• Proportional Choosability: a new list analogue of equitable coloring, (with J. Mudrock^, M. Pelsmajer, R. Reiniger), Discrete Mathematics, 342 (2019), 2371-2383.
  summary:

  In 2003, Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability which prescribes an upper bound on the size of each color class in the list coloring (unlike equitable coloring which prescribes both an upper and lower bound on the sizes of the color classes). In this paper, we motivate and define a new list analogue of equitable coloring called proportional choosability. For each color c in an list assignment L of a graph, let n(c), multiplicity of c, be the number of vertices v whose list L(v) contains c. Given a 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.



• A Simple Characterization of Proportionally 2-Choosable Graphs, (with J. Mudrock^, M. Pelsmajer, R. Reiniger), Graphs and Combinatorics, 36 (2020), 679-687.
  summary:

  We recently introduced proportional choosability, a new list analogue of equitable coloring. Like equitable coloring, and unlike list equitable coloring (a.k.a. equitable choosability), proportional choosability bounds sizes of color classes both from above and from below. See the definitions in the previous paper's summary above. Here we show that a graph is proportionally 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.



• updated! On Equitable List Arboricity of Graphs, (with J. Mudrock, M. Pelsmajer), The Australasian Journal of Combinatorics, 80 (2021), 419-441.
  summary:

  Equitable list arboricity, introduced by Zhang in 2016, generalizes the notion of equitable list coloring by requiring each color class to be acyclic (instead of an independent set), in addition to the usual upper bound on the size of each color class. G is equitably 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.



• updated! Equitable Choosability of Disjoint Unions of Stars, (with J. Mudrock, T. Wagstrom^), Graphs and Combinatorics, 38 (2022), article 163.
  summary:

  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.

Papers on DP-Coloring (correspondence coloring) of Graphs

Counting Problems


• updated! On the Chromatic Polynomial and Counting DP-Colorings of Graphs, (with J. Mudrock), Advances in Applied Mathematics, Volume 123 (2021), article 102131.
  summary:

  The chromatic polynomial of a graph G, P(G,m), counts the number of proper 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, P_L(G,m), is a list coloring analogue of the chromatic polynomial that has been studied since before 1992, primarily through comparisons with the corresponding chromatic polynomial. 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 P_DP(G,m), and ask several fundamental open questions about it, making progress on some of them. Motivated by known results related to the list color function, we show that while the DP color function behaves similar to the list color function for some graphs, there are also some surprising differences.
  
  A central result on the list color function states that P_L(G,m)=P(G,m) whenever m is large enough, but we will show that for any g ≥ 3 there exists a graph, G, with girth g such that P_DP(G,m) < P(G,m) when m is sufficiently large. We also study the asymptotics of P(G,m) - P_DP(G,m) for a fixed graph G.
  
  We use probabilistic arguments to prove a sharp lower bound on P_DP(G,m) which is the same as the lower bound on P(G,m) when G is bipartite, as claimed by the famous Sidorenko's conjecture on counting homomorphisms from a bipartite graph. This bound along with our other results allow us to show that a natural analogue of Sidorenko's conjecture for the DP color function holds only for trees.
  
  We develop techniques to compute P_DP(G,m) exactly and apply them to certain classes of graphs such as chordal graphs (where P_DP(G,m)=P(G,m)), unicyclic graphs (where the answer depends on the parity of its girth), and cycles with a chord (where the answer depends on the parities of the lengths of the two maximal cycles properly contained in such a graph). Finally, we make progress towards showing that for any graph G, there is a p such that P_DP(G∨K_p, m) = P(G∨K_p, m) for large enough m.



• updated! On Polynomial Representations of the DP Color Function: Theta Graphs and Their Generalizations, (with C. Halberg^, A. Liu^, J. Mudrock, P. Shin^, S. Thomason^), Journal of Combinatorics, accepted for publication.
  summary:

  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, P_L(G,m), is a list coloring analogue of the chromatic polynomial that has been studied since before 1992, primarily through comparisons with the corresponding chromatic polynomial. 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 P_DP(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 P_L(G,m), for any g ≥ 3 there exists a graph, G, with girth g such that P_DP(G,m) < P(G,m) when m is sufficiently large. Thus, two fundamental open questions regarding the DP color function are: (i) for which G does there exist an N such that P_DP(G,m) = P(G,m) whenever m > N, (ii) given a graph G does there always exist an N and a polynomial p(m) such that P_DP(G,m) = p(m) whenever m > N?
  
  Generalized Theta graphs, which have been widely studied for many graph theoretic problems, are the main subject of two classical papers on the chromatic polynomial which include the celebrated result that the zeros of the chromatic polynomials of the Generalized Theta graphs are dense in the whole complex plane with the possible exception of the unit disc around the origin (by including the join of Generalized Theta graphs with an edge this extends to all of the complex plane). It is natural to study the DP color function of these graphs, independent of our motivating questions.
  
  In this paper we give exact formulas for the DP color function of a Theta graph based on the parity of its path lengths. This gives an explicit answer, including the formulas for the polynomials that are not the chromatic polynomial, to both the questions above for Theta graphs. This result illustrates the complex relationship that the DP color function has with the structure of odd and even cycles in a graph. From previous work, we know that girth being even forces P_DP(G,m) < P(G,m) when m is sufficiently large, but this result shows girth being odd can lead to complicated behavior. Despite this, in each of the four parity based cases we see that P_DP(G,m) equals a polynomial.
  
  We extend this result to Generalized Theta graphs by characterizing the exact parity condition that ensures the DP color function eventually equals the chromatic polynomial. To answer the second question for Generalized Theta graphs, we confirm it for the larger class of graphs with a feedback vertex set of size one. Even though we do not have an explicit formula for the polynomial p(m) we know its three highest degree terms are the same as those of the corresponding chromatic polynomial. Our proof considers a decomposition of the graph G into a star G₁ and a spanning forest G₀. The problem then reduces to carefully counting the number H₀-colorings of G₀ that are not H-colorings of G, where H₀ is the m-fold cover of G₀ induced by a given m-fold H of G.



• updated! The DP Color Function of Joins and Vertex-Gluings of Graphs, (with J. Becker^, J. Hewitt^, M. Maxfield^, J. Mudrock, D. Spivey^, S. Thomason^, T. Wagstrom^), Discrete Mathematics, 345 (2022), article 113093.
  summary:

  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 P_DP(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 G₁, .... G_n, we define amalgamated cover, a natural analogue of "gluing" m-fold covers of each G_i together so that we get an m-fold cover for any G formed by vertex gluing the graphs G₁, .... G_n; and we define separated covers, a natural analogue of "splitting" an m-fold cover of any G formed by clique-gluing the graphs G₁, .... G_n 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.



• updated! Non-chromatic-adherence of the DP Color Function via Generalized Theta Graphs, (with Manh Vu Bui^, M. Maxfield^, J. Mudrock, Paul Shin^, S. Thomason^), Graphs and Combinatorics, to appear, In press (2023).
  summary:

  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: P_L, the list color function (1990); DP colorings: P_DP, the DP color function (2019), and P_DP^*, the dual DP color function (2021). For any graph G and m, P_DP(G, m) ≤ P_L(G,m) ≤ P(G,m) ≤ P_DP^*(G,m).
  
  A fundamental open question on the list color function asks whether the list color function of a graph and the corresponding chromatic polynomial stay the same after the first point at which they are both nonzero and equal. A function f is 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.



• new! The DP Color Function of Clique-Gluings of Graphs, (with M. Maxfield^, J. Mudrock, S. Thomason^), submitted for publication.
  summary:

  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 P_DP(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 K_p-gluings of graphs. Recently, Becker et. al. asked whether P_DP(G,m) ≤ (Π_{i=1 to n} P_DP(G_i,m))( Π_{i=0 to 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 K_p-gluing of G₁, ...., G_n. Don and Yang (2021) asked a simpler version of the same question as well. In a recent paper, we showed this inequality holds when p=1 (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.



• new! An Algebraic Approach for Counting DP-3-colorings of Sparse Graphs, (with S. Dahlberg and J. Mudrock), submitted for publication.
  summary:

  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 P_DP(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 3^{n - l/2} on P_DP(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 P_DP(G,3) ≥ 3^n/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.

Coloring Problems


• Combinatorial Nullstellensatz and DP-Coloring of Graphs, (with J. Mudrock), Discrete Mathematics, Volume 343 (2020), article 112115.
  summary:

  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.



• updated! Partial DP-Coloring of Graphs, (with J. Mudrock, M. Pelsmajer), Discrete Mathematics, 344 (2021), article 112306.
  summary:

  In 1980 Albertson and Berman introduced partial coloring, and then in 2000, Albertson, Grossman, and Haas introduced partial list coloring. Here we initiate the study of partial coloring for 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 A_L(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, A_L(G,t) ≥ tn/χ_L(G) for each t in {1, ...., χ_L(G)}, where χ_L(G) is the list chromatic number of G. It is now natural to define the partial DP t-chromatic number, A_DP(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 A_DP(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 A_DP(G,2) less than 2n/3, including an infinite family of graphs on 5k vertices, and the cube graph Q₃. We show that the Wagner graph V₈ is partially DP-nice, A_DP(V₈,2)=6, and that V₈ has no induced subgraph with DP-chromatic number 2 and order at least (2/3)|V(V₈)| 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 Q₃, 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∨K_p is partially DP-nice.
  
  We prove that A_DP(G,t) ≥ n/ceiling[χ_DP(G)/t] for each t in {1, ...., χ_DP(G)}. It follows that for any graph G, the inequality A_DP(G,t) ≥ tn/χ_DP(G) holds true for at least half of the values of t. The main tool here is a subadditivity lemma: for any graph G and t1, ...., tk, A_DP(G,t)) ≤ ∑_{i=1 to k}(A_DP(G,ti)) where t = ∑_{i=1 to k}(ti).



• A Note on Fractional DP-Coloring of Graphs, (with J. Mudrock), submitted for publication.
  summary:

  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 2019, Bernshteyn, Kostochka, and Zhu introduced a fractional version of DP-coloring. They showed that unlike the fractional list chromatic number, the fractional DP-chromatic number of a graph G, denoted χ*_DP(G), can be arbitrarily larger than χ*(G), the graph's fractional chromatic number.
  
  Here we show that for any n and m, there is a t such that χ*_DP(K_(n,m)) ≤ (n+1-(1/t)), which gives improved upper bounds for complete bipartite graphs K_(n,m) with small n. We give a probabilistic argument to determine a lower bound on χ*_DP(K_(2,m)) for any m ≥ 3 which again improves the known bounds. We also generalize a result of Alon, Tuza, and Voigt, and in the process, show that χ*_DP(odd cycle) = χ*(odd cycle). We also show that the answer to a DP-coloring analogue of Erdos' 1979 question on fractional chromatic number is negative even for bipartite graphs by showing: for each k ≥ 149, there exists a k-degenerate bipartite graph, G, and a, b such that for k > a/b, G is not (k,1)-DP-colorable, but G is (a,b)-DP-colorable.



• updated! DP-Coloring of Cartesian Product of Graphs, (with J. Mudrock, G. Sharma^, Q. Stratton^), Journal of Graph Theory, to appear, In press (2022).
  summary:

  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 ≥ (P_DP(G, χ_DP(G)+a-1))^a. Recall that P_DP(G,m) is the DP color function of a graph G, DP coloring analogue of the chromatic polynomial, which counts the minimum number of 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(C_2m+2, 1) = P_DP(C_2m+2, 3) = 2^2m+2 - 1.
  
  Finally, we improve the sharpness Theorem when G is a cycle. Using the tools we have described so far, we construct random covers using a combination of random matchings defined using an equivalence relation on an appropriate set of colorings, and matchings defined using canonical and 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(C_m, k) of the form c_k (P_DP(C_m, k+2) / (k+2))^k where the form of c_k depends on the parity of the cycle. In particular we get that for any m, f(C_2m+1, 1) = P_DP(C_2m+1, 3)/3 = (2^2m+1 - 2)/3.

In the list above, ^ indicates a co-author who was a student at the time of writing the paper.

---

Select Presentations

Note that the talks below might contain errors and may not match with the final version of the corresponding papers.

• Polynomial Method for DP colorings of Graphs
  


• Polynomials and Counting List and DP colorings of Graphs- 2023
  


• Chromatic Polynomial and Counting List and DP colorings of Graphs- 2022
  


• Equity in Public Transit Network Design with a view towards Ethics in Mathematical Modeling
  


• Graph Packing and a Generalization of the Theorems of Sauer-Spencer and Brandt
  


• DP Color Function and Chromatic Polynomial - 2021
  


• Chromatic Number of the Square of the Kneser Graph.
  


• Criticality, List Color Function, and List Coloring Cartesian Products of Graphs
  


• The Gap Between the List-Chromatic and Chromatic Numbers
  


• Proportional Choosability: A New List Analogue of Equitable Coloring
  


• Menger Day Talk on my Research for a General Audience
  


• A Short Preliminary talk on Fall Coloring of Graphs
  


• Finding Large Induced Subgraphs: Graph and Hypergraph Knapsack
  


• Resource Allocation under dependencies and the Graph Knapsack Problem
  


• Hidden Pattern in Dynamic Networks: General Audience Talk
  


• Temporal Scale for Dynamic Networks
  


• Graph Packing and Degree Sequences
  


• Guarding an Orthogonal Art Gallery
  


• Finding Maximum Series-Parallel Subgraph
  


• Finding Maximal Bipartite Subgraphs
  


• Finding Large Subgraphs: Algorithms
  


• Graph Packing: Towards Bollobas-Eldridge Conjecture
  


• Graph Packing: Extending the Sauer-Spencer Theorem
  


• Distinguishing Chromatic Number: Breaking Graph Symmetries through Coloring
  


• Kauffman NK Model: A Stochastic Combinatorial Optimization Model for Complex Systems
  

---