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 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 Generalized Knapsack problems, Interdependent network models, Robust optimization for network models, Design of transportation networks with regard to social equity, etc.
new! Some of my current research related to the equitable urban transportation network design was recently highlighted in the university news.
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 application of algebraic techniques from Combinatorial Nullstellensatz and Alon-Tarsi method.
new! Some of my current research related to the algebraic aspects of DP-coloring of graphs was recently highlighted in the department newsletter.
I maintain a widely used list of Journals in discrete mathematics and related fields , which also give an indication of my research interests.
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.
Details forthcoming.
In the meantime, checkout Section 1.3 of the paper.
Details forthcoming.
In the meantime, checkout Sections 1.3 and 1.4 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.