BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Hemanshu Kaul

Hemanshu Kaul appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.CODiscrete MathematicsComputational ComplexityData Structures and Algorithmsmath.OC

Catalog footprint

What is connected

7works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2022arXiv

DP-Coloring Cartesian Products of Graphs

DP-coloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvořák and Postle in 2015. Motivated by results related to list coloring Cartesian products of graphs, we initiate the study of the DP-chromatic number, $χ_{DP}$, of the same. We show that $χ_{DP}(G \square H) \leq \text{min}\{χ_{DP}(G) + \text{col}(H), χ_{DP}(H) + \text{col}(G) \} - 1$ where $\text{col}(H)$ is the coloring number of the graph $H$. We focus on building tools for lower bound arguments for $χ_{DP}(G \square H)$ and use them to show the sharpness of the bound above and its various forms. Our results illustrate that the DP color function of $G$, the DP analogue of the chromatic polynomial, is essential in the study of the DP-chromatic number of the Cartesian product of graphs, including the following question that extends the sharpness problem above and the classical result on gap between list chromatic number and chromatic number: given any graph $G$ and $k \in \mathbb{N}$, what is the smallest $t$ for which $χ_{DP}(G \square K_{k,t})= χ_{DP}(G) + k$?

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The DP Color Function of Joins and Vertex-Gluings of Graphs

DP-coloring (also called correspondence coloring) is a generalization of list coloring that has been widely studied in recent years after its introduction by Dvořák 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, 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, and we study the threshold (smallest $m$) beyond which the DP color function of a graph constructed with these operations equals its chromatic polynomial.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

A linear input dependence model for interdependent networks

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.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Partial DP-Coloring

In 1980, Albertson and Berman introduced partial coloring. In 2000, Albertson, Grossman, and Haas introduced partial list coloring. Here, we initiate the study of partial coloring for an insightful generalization of list coloring introduced in 2015 by Dvořák and Postle, DP-coloring (or correspondence coloring). We consider the DP-coloring analogue of the Partial List Coloring Conjecture, which generalizes a natural bound for partial coloring. We show that while this partial DP-coloring conjecture does not hold, several results on partial list coloring can be extended to partial DP-coloring. We also study partial DP-coloring of the join of a graph with a complete graph, and we present several interesting open questions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Combinatorial Nullstellensatz and DP-coloring of Graphs

We initiate the study of applying the Combinatorial Nullstellensatz to the DP-coloring of graphs even though, as is well-known, the Alon-Tarsi theorem does not apply to DP-coloring. We define the notion of good covers of prime order which allows us to apply the Combinatorial Nullstellensatz to DP-coloring. We apply these tools 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 satisfy $χ_{DP}(G) \leq 3$, and we completely determine the DP-chromatic number of squares of all cycles.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the Chromatic Polynomial and Counting DP-Colorings

The chromatic polynomial of a graph $G$, denoted $P(G,m)$, is equal to the number of proper $m$-colorings of $G$. The list color function of graph $G$, denoted $P_{\ell}(G,m)$, is a list analogue of the chromatic polynomial that has been studied since 1992, primarily through comparisons with the corresponding chromatic polynomial. DP-coloring (also called correspondence coloring) is a generalization of list coloring recently introduced by Dvořák and Postle. 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. For example, Wang, Qian, and Yan recently showed that if $G$ is a connected graph with $l$ edges, then $P_{\ell}(G,m)=P(G,m)$ whenever $m > \frac{l-1}{\ln(1+ \sqrt{2})}$, but we will show that for any $g \geq 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 develop techniques to compute $P_{DP}(G,m)$ exactly and apply them to certain classes of graphs such as chordal graphs, unicyclic graphs, and cycles with a chord. Finally, we make progress towards showing that for any graph $G$, there is a $p$ such that $P_{DP}(G \vee K_p, m) = P(G \vee K_p , m)$ for large enough $m$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Approximating Quadratic 0-1 Programming via SOCP

We consider the problem of approximating Quadratic O-1 Integer Programs with bounded number of constraints and non-negative constraint matrix entries, which we term as PIQP. We describe and analyze a randomized algorithm based on a program with hyperbolic constraints (a Second-Order Cone Programming -SOCP- formulation) that achieves an approximation ratio of $O(a_{max} \frac{n}{β(n)})$, where $a_{max}$ is the maximum size of an entry in the constraint matrix and $β(n) \leq \min_i{W_i} $, where $W_i$ are the constant terms that define the constraint inequalities. We note that by appropriately choosing $β(n)$ the randomized algorithm, when combined with other algorithms that achieve good approximations for smaller values of $ W_i$, allows better algorithms for the complete range of $W_i$. This, together with a greedy algorithm, provides a $O^*(a_{max} n^{1/2} )$ factor approximation, where $O^*$ hides logarithmic terms. 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 concentration bounds provided by Chernoff-Hoeffding and Kim-Vu.

0 citations0 reviewsNo code linkedOpen access